Ćwiczenia/3. Ćwiczenia/Zadanie 4. (scalanie k posortowanych list jednokierunkowych).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaproponować algorytm scalający k posortowanych list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ w zadaniu jest mowa o scalaniu list odsyłaczowych, listy źródłowe są modyfikowane."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja testująca poprawność algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def test_merging(linked_list_creation,     # A class or a function which creates a linked list\n",
    "                 linked_list_to_list,      # A function which converts a linked list to a list\n",
    "                 merge_lists_fn,           # A function which performs merging on sorted linekd lists\n",
    "                 samples=20,               # A number of repetitions (tests performed)\n",
    "                 lists_counts=(0, 10),     # A number of lists created per a test\n",
    "                 lists_lengths=(0, 10),    # A number of elements in each list\n",
    "                 lists_values=(-100, 100), # A renge of which values will be picked to create a test linked list\n",
    "                 failed_only=False         # A flag which indicates if all the results will be printed or only failed\n",
    "                 ):\n",
    "    passed = 0\n",
    "    for i in range(1, samples + 1):\n",
    "        # Create test data\n",
    "        lists = []\n",
    "        all_values = []\n",
    "        input_lists = []\n",
    "        for _ in range(random.randint(*lists_counts)):\n",
    "            values = sorted(random.randint(*lists_values) for _ in range(random.randint(*lists_lengths)))\n",
    "            input_lists.append(values)\n",
    "            all_values.extend(values)\n",
    "            ll_obj = linked_list_creation(values)\n",
    "            lists.append(ll_obj)\n",
    "        # Perform testing\n",
    "        expected = sorted(all_values)\n",
    "        result_ll = merge_lists_fn(lists)\n",
    "        result = linked_list_to_list(result_ll)\n",
    "        is_correct = result == expected\n",
    "        passed += is_correct\n",
    "        # Print information about a test performed\n",
    "        if not failed_only or (failed_only and not is_correct):\n",
    "            print(f'Test #{i}:')\n",
    "            print('Input lists:')\n",
    "            for idx, lst in enumerate(input_lists):\n",
    "                print(f'\\t{idx + 1}.  {lst}')\n",
    "            print('Expected:', expected)\n",
    "            print('Result:  ', result)\n",
    "            print(f'Test {\"PASSED\" if is_correct else \"FAILED\"}')\n",
    "            print(f'Passed to tested ratio: {passed}/{i}', end='\\n\\n')\n",
    "    # Print final results\n",
    "    print('===== Final results: =====')\n",
    "    print(f'Total tests passed: {passed}/{samples}')\n",
    "    print(f'An algorithm is {\"CORRECT\" if passed == samples else \"WRONG\"}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja porównująca wydajność algorytmów"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Uwaga"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poniższa funkcja nie sprawdza poprawności działania algorytmu. Przed przystąpieniem do porównania wydajności, sprawdź poprawność algorytmu, przy pomocy powyższej funkcji."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import time\n",
    "\n",
    "\n",
    "def compare_performance(data, *,\n",
    "                        samples=20,               # A number of repetitions (tests performed)\n",
    "                        lists_counts=(0, 10),     # A number of lists created per a test\n",
    "                        lists_lengths=(0, 10),    # A number of elements in each list\n",
    "                        lists_values=(-100, 100), # A renge of which values will be picked to create a test linked list\n",
    "                        progress_interval=10      # A number of tests that will be performed between showing\n",
    "                       ):\n",
    "    times = dict.fromkeys(data.keys(), 0)\n",
    "    max_algorithm_name_len = max(len(key) for key in data.keys())\n",
    "    \n",
    "    for i in range(1, samples + 1):\n",
    "        # Create test data\n",
    "        input_lists = []\n",
    "        for _ in range(random.randint(*lists_counts)):\n",
    "            values = sorted(random.randint(*lists_values) for _ in range(random.randint(*lists_lengths)))\n",
    "            input_lists.append(values)\n",
    "            \n",
    "        # Perform time testing\n",
    "        for name, (linked_list_creation, merge_lists_fn, globals_) in data.items():\n",
    "            # Overwrite current global values to make an algorithm able to work (use a proper funciton)\n",
    "            for obj_name, obj in globals_.items():\n",
    "                globals()[obj_name] = obj\n",
    "            # Create input linked lists\n",
    "            lists = [linked_list_creation(values) for values in input_lists]\n",
    "            # Perform test\n",
    "            start_time = time.time()\n",
    "            merge_lists_fn(lists)\n",
    "            end_time = time.time()\n",
    "            # Store test results\n",
    "            times[name] += end_time - start_time\n",
    "            \n",
    "        # Print progress if set an interval\n",
    "        if progress_interval > 0 and not i % progress_interval:\n",
    "            print(f\"===== Results after {i} tests: =====\")\n",
    "            for name in sorted(times, key=lambda name: times[name]):\n",
    "                total_time = times[name]\n",
    "                print(f\"{name.rjust(max_algorithm_name_len)}   Total (in seconds): {total_time:.7f} \\tAverage: {total_time/i:.7f}\")\n",
    "            print()\n",
    "            \n",
    "    # Print final results\n",
    "    print(\"===== Final results: =====\")\n",
    "    print(f\"Tests performed: {samples}\")\n",
    "    print(\"Total times (in seconds):\")\n",
    "    for name in sorted(times, key=lambda name: times[name]):\n",
    "        total_time = times[name]\n",
    "        print(f\"\\t{name.rjust(max_algorithm_name_len)}:   {total_time:.7f}\")\n",
    "    print(\"Average times (in seconds):\")\n",
    "    for name in sorted(times, key=lambda name: times[name]):\n",
    "        total_time = times[name]\n",
    "        print(f\"\\t{name.rjust(max_algorithm_name_len)}:   {total_time/samples:.7f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Słownik przechowujący algorytmy do porównania"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "algo_data = {}  # algo_data[<algorithm name>] = (<linked_list_creation>, <merge_lists_fn>, <global objects dict>)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sposób #1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ten sposób polega na iterowaniu przez tablicę (listę), zawierającą wskaźniki do początków (wartowników) $ k $ posortowanych list, a następnie, łączeniu par list odsyłaczowych w jedną większą listę i dorzucanie jej z powrotem do połączenia później. Tzn. łączymy najpierw krótsze listy, tworząc z nich dłuższe i postępujemy tak, aż pozostanie nam jedna lista, będąca listą wynikową."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jest to jeden z bardziej wydajnych sposobów, ktory przypomina nieco Merge Sorta dla list odsyłaczowych, polegającego na łączeniu serii naturalnych. Tutaj mamy od razu dane posortowane listy, więc sytuacja jest jeszcze łatwiejsza i polega jedynie na złączaniu list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zauważmy również, że poniższa implementacja nie potrzebuje rzadnego dodatkowego miejsca, a wszystkie operacje są wykonywane \"w miejscu\" (również przekazana sekwencja wskaźników do list odsyłaczowych zostaje zmodyfikowana)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu #1 (bez tworzenia dodatkowych struktur)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja obiektowa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        \n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self, values: 'iterable' = None):\n",
    "        self.head = self.tail = None\n",
    "        self.length = 0\n",
    "        if values: self.extend(values)\n",
    "        \n",
    "    def __iter__(self):\n",
    "        curr = self.head\n",
    "        while curr:\n",
    "            yield curr.val\n",
    "            curr = curr.next\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    \n",
    "    def extend(self, values: 'iterable'):\n",
    "        if values:\n",
    "            iterator = iter(values)\n",
    "            if not self:\n",
    "                self.head = self.tail = Node(next(iterator))\n",
    "            for val in iterator:\n",
    "                self.tail.next = Node(val)\n",
    "                self.tail = self.tail.next\n",
    "            self.length += len(values)\n",
    "\n",
    "            \n",
    "def merge_sorted_lists_pair(ll1, ll2) -> LinkedList:\n",
    "    # Create a result Linked List with a sentinel node\n",
    "    result_ll = LinkedList([None])\n",
    "    # Update a result linked list's length\n",
    "    result_ll.length = len(ll1) + len(ll2)\n",
    "    # Prepare pointers\n",
    "    ll1_curr = ll1.head\n",
    "    ll2_curr = ll2.head\n",
    "    result_ll_curr = result_ll.head\n",
    "    # Create a result (merged) linked list of two linked lists passed\n",
    "    while ll1_curr and ll2_curr:\n",
    "        if ll1_curr.val < ll2_curr.val:\n",
    "            result_ll_curr.next = ll1_curr\n",
    "            ll1_curr = ll1_curr.next\n",
    "        else:\n",
    "            result_ll_curr.next = ll2_curr\n",
    "            ll2_curr = ll2_curr.next\n",
    "        result_ll_curr = result_ll_curr.next\n",
    "    # Link the remaining parts\n",
    "    if ll1_curr:\n",
    "        result_ll_curr.next = ll1_curr\n",
    "    else:\n",
    "        result_ll_curr.next = ll2_curr\n",
    "    # Unlink a sentinel node from a result linked list\n",
    "    result_ll.head = result_ll.head.next\n",
    "    # Return a linked list created\n",
    "    return result_ll\n",
    "    \n",
    "    \n",
    "def merge_sorted_lists(lls) -> LinkedList:\n",
    "    # Return an empty linked list if there are no input lists or the first list if there is\n",
    "    # only one linked list\n",
    "    if not lls: return LinkedList()\n",
    "    # Else, if there are at least 2 lists, merge them to the one list\n",
    "    interval = 1\n",
    "    amount = len(lls)\n",
    "    while interval < amount:\n",
    "        for i in range(0, amount - interval, 2 * interval):\n",
    "            lls[i] = merge_sorted_lists_pair(lls[i], lls[i + interval])\n",
    "        interval *= 2\n",
    "    \n",
    "    # Return a result of merging all the lists\n",
    "    return lls[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (LinkedList, merge_sorted_lists, {\n",
    "    'merge_sorted_lists_pair': merge_sorted_lists_pair,\n",
    "    'merge_sorted_lists': merge_sorted_lists,\n",
    "    'LinkedList': LinkedList,\n",
    "    'Node': Node\n",
    "})\n",
    "algo_data['(Sposób #1) (Implementacja #1) W miejscu obiektowo'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "\t1.  [54]\n",
      "\t2.  []\n",
      "\t3.  [-91, -5, 99]\n",
      "\t4.  [-51, -38, -27, -6, -2, 9, 29, 37, 92]\n",
      "\t5.  []\n",
      "\t6.  [-78, -61, -56, 2, 24, 34, 78, 99]\n",
      "Expected: [-91, -78, -61, -56, -51, -38, -27, -6, -5, -2, 2, 9, 24, 29, 34, 37, 54, 78, 92, 99, 99]\n",
      "Result:   [-91, -78, -61, -56, -51, -38, -27, -6, -5, -2, 2, 9, 24, 29, 34, 37, 54, 78, 92, 99, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [-89, -67, 41, 55, 68, 69]\n",
      "\t2.  [-52, -37, -20, -11, 2, 34, 35, 55, 74]\n",
      "\t3.  [-79, -64, -13, -8, 12, 35, 56]\n",
      "\t4.  [-61, -52]\n",
      "\t5.  [-91, -87, -42, -26, -12, 21, 45, 46, 67, 86]\n",
      "\t6.  [-96]\n",
      "\t7.  [-82, -37, -11, -9, 59, 63, 88, 88, 93]\n",
      "\t8.  [-76, -48, -6, 2, 5, 29, 36, 59, 88]\n",
      "\t9.  [-59]\n",
      "\t10.  [-52, 1]\n",
      "Expected: [-96, -91, -89, -87, -82, -79, -76, -67, -64, -61, -59, -52, -52, -52, -48, -42, -37, -37, -26, -20, -13, -12, -11, -11, -9, -8, -6, 1, 2, 2, 5, 12, 21, 29, 34, 35, 35, 36, 41, 45, 46, 55, 55, 56, 59, 59, 63, 67, 68, 69, 74, 86, 88, 88, 88, 93]\n",
      "Result:   [-96, -91, -89, -87, -82, -79, -76, -67, -64, -61, -59, -52, -52, -52, -48, -42, -37, -37, -26, -20, -13, -12, -11, -11, -9, -8, -6, 1, 2, 2, 5, 12, 21, 29, 34, 35, 35, 36, 41, 45, 46, 55, 55, 56, 59, 59, 63, 67, 68, 69, 74, 86, 88, 88, 88, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "\t1.  [25, 34, 46, 47, 92, 94]\n",
      "\t2.  [-84, -34, -32, -30, -28, -8, -4, 64, 73, 83]\n",
      "\t3.  [-38, 73, 94]\n",
      "\t4.  [-46, -41, 16, 38, 58, 60, 80, 88]\n",
      "\t5.  [-60]\n",
      "\t6.  [-83, -62, -31, -22, -15, 2, 34, 68]\n",
      "\t7.  [-95, -36, 19, 74, 78]\n",
      "Expected: [-95, -84, -83, -62, -60, -46, -41, -38, -36, -34, -32, -31, -30, -28, -22, -15, -8, -4, 2, 16, 19, 25, 34, 34, 38, 46, 47, 58, 60, 64, 68, 73, 73, 74, 78, 80, 83, 88, 92, 94, 94]\n",
      "Result:   [-95, -84, -83, -62, -60, -46, -41, -38, -36, -34, -32, -31, -30, -28, -22, -15, -8, -4, 2, 16, 19, 25, 34, 34, 38, 46, 47, 58, 60, 64, 68, 73, 73, 74, 78, 80, 83, 88, 92, 94, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "\t1.  [-96, -88, -55, -40, -9, 97, 98]\n",
      "\t2.  [-95, -95, -87, -51, -35, -22, -9, 99]\n",
      "\t3.  [-61, -58, 13, 30, 32, 50, 51]\n",
      "\t4.  [-85, -74, -52, -24, 13, 16, 56, 68, 72, 81]\n",
      "Expected: [-96, -95, -95, -88, -87, -85, -74, -61, -58, -55, -52, -51, -40, -35, -24, -22, -9, -9, 13, 13, 16, 30, 32, 50, 51, 56, 68, 72, 81, 97, 98, 99]\n",
      "Result:   [-96, -95, -95, -88, -87, -85, -74, -61, -58, -55, -52, -51, -40, -35, -24, -22, -9, -9, 13, 13, 16, 30, 32, 50, 51, 56, 68, 72, 81, 97, 98, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "\t1.  [-89, -73, -70, -30, -14, -8, 7, 35, 81, 87]\n",
      "\t2.  [-83]\n",
      "\t3.  [-94, -70, -60, -51, -41, 24, 27, 36, 54, 84]\n",
      "\t4.  [-81, -70, -46, 9, 10, 18, 30, 37, 78]\n",
      "\t5.  [-86, 63]\n",
      "\t6.  [-73, -43, -35, 14, 25, 30, 56, 70, 70]\n",
      "\t7.  [-51, -32, -31, -20, -11, 16, 19, 28]\n",
      "\t8.  [-60, -33, 4, 44, 57, 78]\n",
      "Expected: [-94, -89, -86, -83, -81, -73, -73, -70, -70, -70, -60, -60, -51, -51, -46, -43, -41, -35, -33, -32, -31, -30, -20, -14, -11, -8, 4, 7, 9, 10, 14, 16, 18, 19, 24, 25, 27, 28, 30, 30, 35, 36, 37, 44, 54, 56, 57, 63, 70, 70, 78, 78, 81, 84, 87]\n",
      "Result:   [-94, -89, -86, -83, -81, -73, -73, -70, -70, -70, -60, -60, -51, -51, -46, -43, -41, -35, -33, -32, -31, -30, -20, -14, -11, -8, 4, 7, 9, 10, 14, 16, 18, 19, 24, 25, 27, 28, 30, 30, 35, 36, 37, 44, 54, 56, 57, 63, 70, 70, 78, 78, 81, 84, 87]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "\t1.  [-65, -33, -12, -7, 33, 40, 51, 67, 77, 82]\n",
      "\t2.  [-98, -91, -60, -54, -47, -4, -1, 14, 61, 69]\n",
      "\t3.  [-87, -71, -69, 45, 51, 58, 67, 87, 91]\n",
      "\t4.  [-32, 9, 25]\n",
      "\t5.  [-77, -56, -26, 92, 93]\n",
      "\t6.  []\n",
      "Expected: [-98, -91, -87, -77, -71, -69, -65, -60, -56, -54, -47, -33, -32, -26, -12, -7, -4, -1, 9, 14, 25, 33, 40, 45, 51, 51, 58, 61, 67, 67, 69, 77, 82, 87, 91, 92, 93]\n",
      "Result:   [-98, -91, -87, -77, -71, -69, -65, -60, -56, -54, -47, -33, -32, -26, -12, -7, -4, -1, 9, 14, 25, 33, 40, 45, 51, 51, 58, 61, 67, 67, 69, 77, 82, 87, 91, 92, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "\t1.  [-79, -10, 82]\n",
      "\t2.  [-88, -71, -39, -10, 47, 48]\n",
      "\t3.  [-96, -68, -53, -53, -47, 30, 93, 93]\n",
      "\t4.  [-60, -43, 36, 38, 65, 96, 100]\n",
      "\t5.  [-60, -52, -34, -31, -23, 64, 79]\n",
      "\t6.  [-77, -51, -49, -20, 21, 39, 41, 42, 79, 89]\n",
      "Expected: [-96, -88, -79, -77, -71, -68, -60, -60, -53, -53, -52, -51, -49, -47, -43, -39, -34, -31, -23, -20, -10, -10, 21, 30, 36, 38, 39, 41, 42, 47, 48, 64, 65, 79, 79, 82, 89, 93, 93, 96, 100]\n",
      "Result:   [-96, -88, -79, -77, -71, -68, -60, -60, -53, -53, -52, -51, -49, -47, -43, -39, -34, -31, -23, -20, -10, -10, 21, 30, 36, 38, 39, 41, 42, 47, 48, 64, 65, 79, 79, 82, 89, 93, 93, 96, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "\t1.  [45]\n",
      "\t2.  [-59, -36, -36, -4, 17]\n",
      "Expected: [-59, -36, -36, -4, 17, 45]\n",
      "Result:   [-59, -36, -36, -4, 17, 45]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "\t1.  [-100, -89, -77, -68, -49, -43, -26, -8, -8, 5]\n",
      "Expected: [-100, -89, -77, -68, -49, -43, -26, -8, -8, 5]\n",
      "Result:   [-100, -89, -77, -68, -49, -43, -26, -8, -8, 5]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  [-87, 28, 64]\n",
      "\t2.  [-75, -31, 9, 18, 30, 40, 55]\n",
      "\t3.  []\n",
      "\t4.  [-84, -74, -55, -1, 36, 47, 63, 73, 91]\n",
      "\t5.  [-96, -58, -50, -47, -45, -26, 3, 44, 63, 90]\n",
      "Expected: [-96, -87, -84, -75, -74, -58, -55, -50, -47, -45, -31, -26, -1, 3, 9, 18, 28, 30, 36, 40, 44, 47, 55, 63, 63, 64, 73, 90, 91]\n",
      "Result:   [-96, -87, -84, -75, -74, -58, -55, -50, -47, -45, -31, -26, -1, 3, 9, 18, 28, 30, 36, 40, 44, 47, 55, 63, 63, 64, 73, 90, 91]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  [32, 52, 61]\n",
      "\t2.  [-77, -53, -39, -25, -9, 9, 59, 68, 85]\n",
      "\t3.  []\n",
      "\t4.  []\n",
      "\t5.  [-92, -48, -28]\n",
      "\t6.  [84]\n",
      "\t7.  [-67, -49, -7, 54, 80]\n",
      "\t8.  [-95]\n",
      "Expected: [-95, -92, -77, -67, -53, -49, -48, -39, -28, -25, -9, -7, 9, 32, 52, 54, 59, 61, 68, 80, 84, 85]\n",
      "Result:   [-95, -92, -77, -67, -53, -49, -48, -39, -28, -25, -9, -7, 9, 32, 52, 54, 59, 61, 68, 80, 84, 85]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [-91, -91, -78, -73, -11, 4, 6, 7, 56, 74]\n",
      "\t2.  [-100, -63, -58, -57, 32, 33]\n",
      "\t3.  [-47, -34, 14, 68]\n",
      "\t4.  [52, 76]\n",
      "\t5.  [-74, -34, -9]\n",
      "\t6.  [-39, -28, -15, -3, 38, 84, 88]\n",
      "\t7.  [-74, -21, -14, 27, 31, 49, 57, 74]\n",
      "\t8.  [-70, -64, 3, 3, 7, 14, 50]\n",
      "\t9.  [-16, 26, 61, 67]\n",
      "Expected: [-100, -91, -91, -78, -74, -74, -73, -70, -64, -63, -58, -57, -47, -39, -34, -34, -28, -21, -16, -15, -14, -11, -9, -3, 3, 3, 4, 6, 7, 7, 14, 14, 26, 27, 31, 32, 33, 38, 49, 50, 52, 56, 57, 61, 67, 68, 74, 74, 76, 84, 88]\n",
      "Result:   [-100, -91, -91, -78, -74, -74, -73, -70, -64, -63, -58, -57, -47, -39, -34, -34, -28, -21, -16, -15, -14, -11, -9, -3, 3, 3, 4, 6, 7, 7, 14, 14, 26, 27, 31, 32, 33, 38, 49, 50, 52, 56, 57, 61, 67, 68, 74, 74, 76, 84, 88]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-98]\n",
      "\t2.  []\n",
      "\t3.  [-47, 48, 79]\n",
      "\t4.  [-72, -71, -60, 17, 22, 28, 54]\n",
      "Expected: [-98, -72, -71, -60, -47, 17, 22, 28, 48, 54, 79]\n",
      "Result:   [-98, -72, -71, -60, -47, 17, 22, 28, 48, 54, 79]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  [24, 91]\n",
      "\t2.  [-44, -15, -14, 7, 67, 88, 92]\n",
      "\t3.  [-16, -2, 51, 54, 100]\n",
      "\t4.  [-99, -98, -92, -62, -62, -53, 54, 91, 93]\n",
      "\t5.  [-59, 51, 57, 97]\n",
      "\t6.  [-80, 96]\n",
      "\t7.  [-92, -75, -30, 21, 52]\n",
      "\t8.  []\n",
      "\t9.  [-96, -72, -36, 11, 65, 86, 100]\n",
      "Expected: [-99, -98, -96, -92, -92, -80, -75, -72, -62, -62, -59, -53, -44, -36, -30, -16, -15, -14, -2, 7, 11, 21, 24, 51, 51, 52, 54, 54, 57, 65, 67, 86, 88, 91, 91, 92, 93, 96, 97, 100, 100]\n",
      "Result:   [-99, -98, -96, -92, -92, -80, -75, -72, -62, -62, -59, -53, -44, -36, -30, -16, -15, -14, -2, 7, 11, 21, 24, 51, 51, 52, 54, 54, 57, 65, 67, 86, 88, 91, 91, 92, 93, 96, 97, 100, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "\t1.  [-82, -60]\n",
      "\t2.  [-70, -65, -57, -17, -13, 14, 41, 75]\n",
      "\t3.  [-23, -22, 16, 18, 94]\n",
      "\t4.  [-90, -63, -56, -31, -23, 15, 39, 67, 82, 85]\n",
      "\t5.  []\n",
      "\t6.  [-70, -51, -50, -20, 16, 20, 22, 40, 85, 93]\n",
      "Expected: [-90, -82, -70, -70, -65, -63, -60, -57, -56, -51, -50, -31, -23, -23, -22, -20, -17, -13, 14, 15, 16, 16, 18, 20, 22, 39, 40, 41, 67, 75, 82, 85, 85, 93, 94]\n",
      "Result:   [-90, -82, -70, -70, -65, -63, -60, -57, -56, -51, -50, -31, -23, -23, -22, -20, -17, -13, 14, 15, 16, 16, 18, 20, 22, 39, 40, 41, 67, 75, 82, 85, 85, 93, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-42, 16, 27, 83]\n",
      "\t2.  []\n",
      "\t3.  [-87, -86, -56, -32, -30, -26, -14, 30, 52, 79]\n",
      "\t4.  [-94, -70, -68, -27, 41, 70, 96, 97]\n",
      "Expected: [-94, -87, -86, -70, -68, -56, -42, -32, -30, -27, -26, -14, 16, 27, 30, 41, 52, 70, 79, 83, 96, 97]\n",
      "Result:   [-94, -87, -86, -70, -68, -56, -42, -32, -30, -27, -26, -14, 16, 27, 30, 41, 52, 70, 79, 83, 96, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  [-90, -16, 7, 19, 62, 72]\n",
      "\t2.  [-19, 3, 17]\n",
      "\t3.  [-97, -70, 78]\n",
      "\t4.  [12, 29, 70, 93]\n",
      "\t5.  [-59]\n",
      "\t6.  [-12]\n",
      "\t7.  [-77, -49, 12, 35, 52, 77, 87]\n",
      "\t8.  [-99, -90, -58, -52, -4, 21]\n",
      "Expected: [-99, -97, -90, -90, -77, -70, -59, -58, -52, -49, -19, -16, -12, -4, 3, 7, 12, 12, 17, 19, 21, 29, 35, 52, 62, 70, 72, 77, 78, 87, 93]\n",
      "Result:   [-99, -97, -90, -90, -77, -70, -59, -58, -52, -49, -19, -16, -12, -4, 3, 7, 12, 12, 17, 19, 21, 29, 35, 52, 62, 70, 72, 77, 78, 87, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "\t1.  [-95, -76, -50, -43, -19, -16, 1, 50, 73, 92]\n",
      "\t2.  []\n",
      "\t3.  [-94, -76, -74, -63, -54, -45]\n",
      "\t4.  [-5, 6, 14]\n",
      "Expected: [-95, -94, -76, -76, -74, -63, -54, -50, -45, -43, -19, -16, -5, 1, 6, 14, 50, 73, 92]\n",
      "Result:   [-95, -94, -76, -76, -74, -63, -54, -50, -45, -43, -19, -16, -5, 1, 6, 14, 50, 73, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(LinkedList, list, merge_sorted_lists)\n",
    "# test_merging(LinkedList, list, merge_sorted_lists,\n",
    "#             samples=1000, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja funkcyjna"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def create_linked_list(values: 'iterable' = None) -> 'linked list head (sentinel)':\n",
    "    head = Node()  # A sentinel node\n",
    "    if not values: return head\n",
    "    head.next = curr = Node(values[0])\n",
    "    for i in range(1, len(values)):\n",
    "        curr.next = Node(values[i])\n",
    "        curr = curr.next\n",
    "    return head\n",
    "\n",
    "\n",
    "def merge_sorted_lists_pair(ll1_head, ll2_head) -> 'linked list head (sentinel)':\n",
    "    ll_res_head = Node()  # Store a sentinel node\n",
    "\n",
    "    ll_res_curr = ll_res_head\n",
    "    ll1_curr = ll1_head.next\n",
    "    ll2_curr = ll2_head.next\n",
    "\n",
    "    while ll1_curr and ll2_curr:\n",
    "        if ll1_curr.val < ll2_curr.val:\n",
    "            ll_res_curr.next = ll1_curr\n",
    "            ll1_curr = ll1_curr.next\n",
    "        else:\n",
    "            ll_res_curr.next = ll2_curr\n",
    "            ll2_curr = ll2_curr.next\n",
    "        ll_res_curr = ll_res_curr.next\n",
    "\n",
    "    # Link a remaining part to a result linked list\n",
    "    if ll1_curr:\n",
    "        ll_res_curr.next = ll1_curr\n",
    "    else:\n",
    "        ll_res_curr.next = ll2_curr\n",
    "\n",
    "    return ll_res_head\n",
    "\n",
    "\n",
    "def merge_sorted_lists(lls) -> 'linked list head (sentinel)':\n",
    "    # Return an empty linked list sentinel node if there are no linked lists in lls iterable\n",
    "    if not lls: return Node()\n",
    "    # Else, if there are at least 2 lists, merge them to the one list\n",
    "    interval = 1\n",
    "    amount = len(lls)\n",
    "    while interval < amount:\n",
    "        for i in range(0, amount - interval, 2 * interval):\n",
    "            lls[i] = merge_sorted_lists_pair(lls[i], lls[i + interval])\n",
    "        interval *= 2\n",
    "    \n",
    "    # Return a result of merging all the lists\n",
    "    return lls[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja pomocnicza, konwertująca listę odsyłaczową do listy Pythonowej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linked_list_to_list(ll_head: 'linked list head (sentinel)') -> list:\n",
    "    result = []\n",
    "    curr = ll_head.next\n",
    "    while curr:\n",
    "        result.append(curr.val)\n",
    "        curr = curr.next\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (create_linked_list, merge_sorted_lists, {\n",
    "    'merge_sorted_lists_pair': merge_sorted_lists_pair,\n",
    "    'merge_sorted_lists': merge_sorted_lists,\n",
    "    'create_linked_list': create_linked_list,\n",
    "    'linked_list_to_list': linked_list_to_list,\n",
    "    'Node': Node\n",
    "})\n",
    "algo_data['(Sposób #1) (Implementacja #1) W miejscu funkcyjnie'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "\t1.  [-22]\n",
      "\t2.  [-33, -12, -10, 97]\n",
      "\t3.  [-91, -85, -62, -12, -7, -6, 54, 87, 95]\n",
      "\t4.  [-72, -4, 0, 25]\n",
      "\t5.  [-55, -22, -18, 18, 22, 64, 66, 94]\n",
      "\t6.  [47, 54, 90]\n",
      "\t7.  [-85, 48, 68, 92]\n",
      "\t8.  [-66, -53, -9, 26, 38, 45, 65, 66, 85, 92]\n",
      "\t9.  [-76]\n",
      "\t10.  [-79, -75, -25, -13, 15, 37, 37]\n",
      "Expected: [-91, -85, -85, -79, -76, -75, -72, -66, -62, -55, -53, -33, -25, -22, -22, -18, -13, -12, -12, -10, -9, -7, -6, -4, 0, 15, 18, 22, 25, 26, 37, 37, 38, 45, 47, 48, 54, 54, 64, 65, 66, 66, 68, 85, 87, 90, 92, 92, 94, 95, 97]\n",
      "Result:   [-91, -85, -85, -79, -76, -75, -72, -66, -62, -55, -53, -33, -25, -22, -22, -18, -13, -12, -12, -10, -9, -7, -6, -4, 0, 15, 18, 22, 25, 26, 37, 37, 38, 45, 47, 48, 54, 54, 64, 65, 66, 66, 68, 85, 87, 90, 92, 92, 94, 95, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [-86, 42, 54, 91]\n",
      "\t2.  [-93, -78, -71, -62, -58, -58, -48, -46, -14, 90]\n",
      "\t3.  [-92, -9, 61]\n",
      "\t4.  [-95, -67, -44, 25, 37, 53]\n",
      "\t5.  [-89, -84, 39, 58, 67, 76, 95]\n",
      "\t6.  [-91, -14, 28]\n",
      "Expected: [-95, -93, -92, -91, -89, -86, -84, -78, -71, -67, -62, -58, -58, -48, -46, -44, -14, -14, -9, 25, 28, 37, 39, 42, 53, 54, 58, 61, 67, 76, 90, 91, 95]\n",
      "Result:   [-95, -93, -92, -91, -89, -86, -84, -78, -71, -67, -62, -58, -58, -48, -46, -44, -14, -14, -9, 25, 28, 37, 39, 42, 53, 54, 58, 61, 67, 76, 90, 91, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "\t1.  [-45, 86]\n",
      "\t2.  [-90, -89, 88]\n",
      "\t3.  [-24]\n",
      "\t4.  [-16, 52, 53]\n",
      "\t5.  [-90, -70, -67, -63, -28, -6, 9, 16, 51, 70]\n",
      "Expected: [-90, -90, -89, -70, -67, -63, -45, -28, -24, -16, -6, 9, 16, 51, 52, 53, 70, 86, 88]\n",
      "Result:   [-90, -90, -89, -70, -67, -63, -45, -28, -24, -16, -6, 9, 16, 51, 52, 53, 70, 86, 88]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "\t1.  [-28, 2, 33]\n",
      "\t2.  [-6, 67]\n",
      "\t3.  [-92, -86, -1, 29, 56, 59, 78, 87, 91]\n",
      "\t4.  [-2, 26, 78]\n",
      "\t5.  [-47, -19, 28, 32, 40, 52, 56, 71, 74, 79]\n",
      "\t6.  [-43]\n",
      "\t7.  []\n",
      "\t8.  [-75, -45, -41, -30, 50, 78]\n",
      "\t9.  []\n",
      "Expected: [-92, -86, -75, -47, -45, -43, -41, -30, -28, -19, -6, -2, -1, 2, 26, 28, 29, 32, 33, 40, 50, 52, 56, 56, 59, 67, 71, 74, 78, 78, 78, 79, 87, 91]\n",
      "Result:   [-92, -86, -75, -47, -45, -43, -41, -30, -28, -19, -6, -2, -1, 2, 26, 28, 29, 32, 33, 40, 50, 52, 56, 56, 59, 67, 71, 74, 78, 78, 78, 79, 87, 91]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "\t1.  [-87, -71, -57, -45, -45, -19, -12, 55]\n",
      "Expected: [-87, -71, -57, -45, -45, -19, -12, 55]\n",
      "Result:   [-87, -71, -57, -45, -45, -19, -12, 55]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "\t1.  [-49, 75, 95]\n",
      "\t2.  [-92, -23, 87]\n",
      "\t3.  [-69, -15, 8, 30]\n",
      "\t4.  [-52, -30, -5, 40, 100]\n",
      "\t5.  [57, 78, 87, 91]\n",
      "\t6.  [-5, 5, 82]\n",
      "\t7.  [-100, 74, 81]\n",
      "\t8.  [-45, -40, 26, 97]\n",
      "\t9.  [13, 48, 54, 71]\n",
      "\t10.  [-86, -57, -36, 25, 32, 73, 91]\n",
      "Expected: [-100, -92, -86, -69, -57, -52, -49, -45, -40, -36, -30, -23, -15, -5, -5, 5, 8, 13, 25, 26, 30, 32, 40, 48, 54, 57, 71, 73, 74, 75, 78, 81, 82, 87, 87, 91, 91, 95, 97, 100]\n",
      "Result:   [-100, -92, -86, -69, -57, -52, -49, -45, -40, -36, -30, -23, -15, -5, -5, 5, 8, 13, 25, 26, 30, 32, 40, 48, 54, 57, 71, 73, 74, 75, 78, 81, 82, 87, 87, 91, 91, 95, 97, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "\t1.  [-81, -74, -46, -27, -2, 11, 49, 76, 81, 97]\n",
      "\t2.  [-51, -44, 8, 87]\n",
      "\t3.  [-79, -8, 17, 53, 67, 75, 82]\n",
      "Expected: [-81, -79, -74, -51, -46, -44, -27, -8, -2, 8, 11, 17, 49, 53, 67, 75, 76, 81, 82, 87, 97]\n",
      "Result:   [-81, -79, -74, -51, -46, -44, -27, -8, -2, 8, 11, 17, 49, 53, 67, 75, 76, 81, 82, 87, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  [-80, -9, 9, 97]\n",
      "\t2.  [-94, -63, -61, -48, -31, -27, 73, 89, 91]\n",
      "\t3.  [15]\n",
      "\t4.  [-81, -58, -3, 25, 70, 73]\n",
      "\t5.  [-95, -6, 58, 60, 61, 74, 88, 89]\n",
      "\t6.  [-100, 7, 73]\n",
      "\t7.  [-66, 59]\n",
      "\t8.  [-28, -23, 13, 53, 55, 73, 79, 85, 92, 96]\n",
      "\t9.  [-79, -65, 21, 42]\n",
      "\t10.  [-95, -75, -35]\n",
      "Expected: [-100, -95, -95, -94, -81, -80, -79, -75, -66, -65, -63, -61, -58, -48, -35, -31, -28, -27, -23, -9, -6, -3, 7, 9, 13, 15, 21, 25, 42, 53, 55, 58, 59, 60, 61, 70, 73, 73, 73, 73, 74, 79, 85, 88, 89, 89, 91, 92, 96, 97]\n",
      "Result:   [-100, -95, -95, -94, -81, -80, -79, -75, -66, -65, -63, -61, -58, -48, -35, -31, -28, -27, -23, -9, -6, -3, 7, 9, 13, 15, 21, 25, 42, 53, 55, 58, 59, 60, 61, 70, 73, 73, 73, 73, 74, 79, 85, 88, 89, 89, 91, 92, 96, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  [-87, -84, 28, 66]\n",
      "Expected: [-87, -84, 28, 66]\n",
      "Result:   [-87, -84, 28, 66]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [35]\n",
      "\t2.  [-94, 20]\n",
      "\t3.  [30, 46]\n",
      "\t4.  [-91, -71, 28, 32, 92]\n",
      "\t5.  [-100, -91, -56, 16, 34, 92]\n",
      "\t6.  [-98, -82, 4, 87, 98]\n",
      "\t7.  [-56, -52, -17, 21, 29, 35, 55, 65, 69, 93]\n",
      "\t8.  [-30, 79, 83]\n",
      "\t9.  [-88, -87, -83, 22, 41]\n",
      "Expected: [-100, -98, -94, -91, -91, -88, -87, -83, -82, -71, -56, -56, -52, -30, -17, 4, 16, 20, 21, 22, 28, 29, 30, 32, 34, 35, 35, 41, 46, 55, 65, 69, 79, 83, 87, 92, 92, 93, 98]\n",
      "Result:   [-100, -98, -94, -91, -91, -88, -87, -83, -82, -71, -56, -56, -52, -30, -17, 4, 16, 20, 21, 22, 28, 29, 30, 32, 34, 35, 35, 41, 46, 55, 65, 69, 79, 83, 87, 92, 92, 93, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-40, -7, 55]\n",
      "\t2.  [-68, -58, -58, -57, -46, -20, 34, 49, 88, 98]\n",
      "Expected: [-68, -58, -58, -57, -46, -40, -20, -7, 34, 49, 55, 88, 98]\n",
      "Result:   [-68, -58, -58, -57, -46, -40, -20, -7, 34, 49, 55, 88, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  [-85, -45, -19, -14, 4, 7, 27, 85, 95]\n",
      "\t2.  [-90, -64, -31, 39, 49, 77, 96]\n",
      "\t3.  []\n",
      "\t4.  [-71]\n",
      "\t5.  [-84, -52, -32, 22, 51]\n",
      "\t6.  [-74, -1, 60, 64, 64, 67]\n",
      "\t7.  [-67, -26, -17, 83]\n",
      "Expected: [-90, -85, -84, -74, -71, -67, -64, -52, -45, -32, -31, -26, -19, -17, -14, -1, 4, 7, 22, 27, 39, 49, 51, 60, 64, 64, 67, 77, 83, 85, 95, 96]\n",
      "Result:   [-90, -85, -84, -74, -71, -67, -64, -52, -45, -32, -31, -26, -19, -17, -14, -1, 4, 7, 22, 27, 39, 49, 51, 60, 64, 64, 67, 77, 83, 85, 95, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-55, -43, -19, 0, 27, 35, 59, 71, 76, 82]\n",
      "\t2.  [-18]\n",
      "\t3.  [-97, -91, -70, -37, -25, -23, 38, 60]\n",
      "\t4.  [-70, 28, 29, 94]\n",
      "\t5.  [-60, -23, 2, 59, 73]\n",
      "\t6.  []\n",
      "Expected: [-97, -91, -70, -70, -60, -55, -43, -37, -25, -23, -23, -19, -18, 0, 2, 27, 28, 29, 35, 38, 59, 59, 60, 71, 73, 76, 82, 94]\n",
      "Result:   [-97, -91, -70, -70, -60, -55, -43, -37, -25, -23, -23, -19, -18, 0, 2, 27, 28, 29, 35, 38, 59, 59, 60, 71, 73, 76, 82, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "\t1.  [-65, -52, -21, 1, 45]\n",
      "\t2.  [-93, -89, -63, -28]\n",
      "\t3.  [-29]\n",
      "Expected: [-93, -89, -65, -63, -52, -29, -28, -21, 1, 45]\n",
      "Result:   [-93, -89, -65, -63, -52, -29, -28, -21, 1, 45]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  [-69, -69, -69, -31, 9, 80, 87, 88, 99]\n",
      "\t2.  []\n",
      "\t3.  [-63, -60, -58, -10, 2, 10, 60, 81]\n",
      "\t4.  []\n",
      "\t5.  []\n",
      "\t6.  [-76]\n",
      "\t7.  [-76, -54, -34, -8, 23, 70]\n",
      "Expected: [-76, -76, -69, -69, -69, -63, -60, -58, -54, -34, -31, -10, -8, 2, 9, 10, 23, 60, 70, 80, 81, 87, 88, 99]\n",
      "Result:   [-76, -76, -69, -69, -69, -63, -60, -58, -54, -34, -31, -10, -8, 2, 9, 10, 23, 60, 70, 80, 81, 87, 88, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "\t1.  [-90, -17, 39, 53, 83]\n",
      "\t2.  [29, 47]\n",
      "Expected: [-90, -17, 29, 39, 47, 53, 83]\n",
      "Result:   [-90, -17, 29, 39, 47, 53, 83]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(create_linked_list, linked_list_to_list, merge_sorted_lists)\n",
    "# test_merging(LinkedList, list, merge_sorted_lists,\n",
    "#             samples=1000, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu #2 (z użyciem kolejki, lepsza, bo nie tworzy za każdym razem nowej tablicy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja obiektowa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        \n",
    "        \n",
    "class Queue:\n",
    "    def __init__(self, values: 'iterable' = None):\n",
    "        self.head = self.tail = None\n",
    "        self.length = 0\n",
    "        if values: self.enqueue_many(values)\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    \n",
    "    def enqueue(self, val: object):\n",
    "        node = Node(val)\n",
    "        if not self:\n",
    "            self.head = self.tail = node\n",
    "        else:\n",
    "            self.tail.next = node\n",
    "            self.tail = node\n",
    "        self.length += 1\n",
    "        \n",
    "    def dequeue(self) -> object:\n",
    "        if not self:\n",
    "            raise IndexError(f'dequeue from an empty {self.__class__.__name__}')\n",
    "        removed = self.head.val\n",
    "        if len(self) == 1:\n",
    "            self.head = self.tail = None\n",
    "        else:\n",
    "            self.head = self.head.next\n",
    "        self.length -= 1\n",
    "        return removed\n",
    "    \n",
    "    def enqueue_many(self, values: 'iterable'):\n",
    "        if values:\n",
    "            iterator = iter(values)\n",
    "            if not self:\n",
    "                self.head = self.tail = Node(next(iterator))\n",
    "            for val in iterator:\n",
    "                self.tail.next = Node(val)\n",
    "                self.tail = self.tail.next\n",
    "            self.length += len(values)\n",
    "            \n",
    "            \n",
    "class LinkedList:\n",
    "    def __init__(self, values: 'iterable' = None):\n",
    "        self.head = self.tail = None\n",
    "        self.length = 0\n",
    "        if values: self.extend(values)\n",
    "        \n",
    "    def __iter__(self):\n",
    "        curr = self.head\n",
    "        while curr:\n",
    "            yield curr.val\n",
    "            curr = curr.next\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    \n",
    "    def extend(self, values: 'iterable'):\n",
    "        if values:\n",
    "            iterator = iter(values)\n",
    "            if not self:\n",
    "                self.head = self.tail = Node(next(iterator))\n",
    "            for val in iterator:\n",
    "                self.tail.next = Node(val)\n",
    "                self.tail = self.tail.next\n",
    "            self.length += len(values)\n",
    "            \n",
    "            \n",
    "def merge_sorted_lists_pair(ll1, ll2) -> LinkedList:\n",
    "    # Create a result Linked List with a sentinel node\n",
    "    result_ll = LinkedList([None])\n",
    "    # Update a result linked list's length\n",
    "    result_ll.length = len(ll1) + len(ll2)\n",
    "    # Prepare pointers\n",
    "    ll1_curr = ll1.head\n",
    "    ll2_curr = ll2.head\n",
    "    result_ll_curr = result_ll.head\n",
    "    # Create a result (merged) linked list of two linked lists passed\n",
    "    while ll1_curr and ll2_curr:\n",
    "        if ll1_curr.val < ll2_curr.val:\n",
    "            result_ll_curr.next = ll1_curr\n",
    "            ll1_curr = ll1_curr.next\n",
    "        else:\n",
    "            result_ll_curr.next = ll2_curr\n",
    "            ll2_curr = ll2_curr.next\n",
    "        result_ll_curr = result_ll_curr.next\n",
    "    # Link the remaining parts\n",
    "    if ll1_curr:\n",
    "        result_ll_curr.next = ll1_curr\n",
    "    else:\n",
    "        result_ll_curr.next = ll2_curr\n",
    "    # Unlink a sentinel node from a result linked list\n",
    "    result_ll.head = result_ll.head.next\n",
    "    # Return a linked list created\n",
    "    return result_ll\n",
    "    \n",
    "    \n",
    "def merge_sorted_lists(lls) -> LinkedList:\n",
    "    # Return an empty linked list if there are no input lists or the first list if there is\n",
    "    # only one linked list\n",
    "    if not lls: return LinkedList()\n",
    "    # Else, if there are at least 2 lists, merge them to the one list\n",
    "    queue = Queue(lls)\n",
    "    while len(queue) > 1:\n",
    "        # Merge adjacent linked lists and add them to the queue\n",
    "        ll1 = queue.dequeue()\n",
    "        ll2 = queue.dequeue()\n",
    "        queue.enqueue(merge_sorted_lists_pair(ll1, ll2))\n",
    "    \n",
    "    # Return a result of merging all the lists\n",
    "    return queue.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (LinkedList, merge_sorted_lists, {\n",
    "    'merge_sorted_lists_pair': merge_sorted_lists_pair,\n",
    "    'merge_sorted_lists': merge_sorted_lists,\n",
    "    'LinkedList': LinkedList,\n",
    "    'Queue': Queue,\n",
    "    'Node': Node\n",
    "})\n",
    "algo_data['(Sposób #1) (Implementacja #2) Z kolejką obiektowo'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "\t1.  [-69, -55, -13, 2, 11, 31, 97, 98]\n",
      "Expected: [-69, -55, -13, 2, 11, 31, 97, 98]\n",
      "Result:   [-69, -55, -13, 2, 11, 31, 97, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [-87, -54, 16, 83]\n",
      "\t2.  [-33, -9]\n",
      "\t3.  [-99, -85, -69, -60, -32, -10, 32]\n",
      "\t4.  [-32, 9, 72, 79]\n",
      "\t5.  []\n",
      "\t6.  [-49]\n",
      "Expected: [-99, -87, -85, -69, -60, -54, -49, -33, -32, -32, -10, -9, 9, 16, 32, 72, 79, 83]\n",
      "Result:   [-99, -87, -85, -69, -60, -54, -49, -33, -32, -32, -10, -9, 9, 16, 32, 72, 79, 83]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "\t1.  [-66, -51, -24, -15, -6, -3, 38, 43]\n",
      "\t2.  [-88, -62, -2, 9, 35, 63, 88]\n",
      "Expected: [-88, -66, -62, -51, -24, -15, -6, -3, -2, 9, 35, 38, 43, 63, 88]\n",
      "Result:   [-88, -66, -62, -51, -24, -15, -6, -3, -2, 9, 35, 38, 43, 63, 88]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "\t1.  [-99, -88, -36, -35, -1, 17, 47, 47, 52, 58]\n",
      "\t2.  []\n",
      "\t3.  [-88, -11, 70]\n",
      "\t4.  [16, 45]\n",
      "\t5.  [-72, -47, -41, -40, 6, 30, 34]\n",
      "\t6.  [30, 92]\n",
      "\t7.  [-83, -69, 29]\n",
      "\t8.  []\n",
      "Expected: [-99, -88, -88, -83, -72, -69, -47, -41, -40, -36, -35, -11, -1, 6, 16, 17, 29, 30, 30, 34, 45, 47, 47, 52, 58, 70, 92]\n",
      "Result:   [-99, -88, -88, -83, -72, -69, -47, -41, -40, -36, -35, -11, -1, 6, 16, 17, 29, 30, 30, 34, 45, 47, 47, 52, 58, 70, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "\t1.  [-83, -80, -69, 68, 76]\n",
      "\t2.  [-65, -26, -23, -21, 32, 33, 41]\n",
      "\t3.  [-45, -23, 0, 21, 36, 43, 63, 78]\n",
      "\t4.  [-98, -92, -29, 38]\n",
      "\t5.  [-89, -36, -15, 22, 92]\n",
      "\t6.  [-54, -42, -38, -21, -20, 7, 28, 74, 92, 100]\n",
      "\t7.  [-98, -86, -85, -75, -49, -48, 10, 45, 52, 59]\n",
      "\t8.  [-36, 31, 74, 79]\n",
      "\t9.  [44]\n",
      "\t10.  [-96, -40, 10, 18, 19, 27, 64, 74]\n",
      "Expected: [-98, -98, -96, -92, -89, -86, -85, -83, -80, -75, -69, -65, -54, -49, -48, -45, -42, -40, -38, -36, -36, -29, -26, -23, -23, -21, -21, -20, -15, 0, 7, 10, 10, 18, 19, 21, 22, 27, 28, 31, 32, 33, 36, 38, 41, 43, 44, 45, 52, 59, 63, 64, 68, 74, 74, 74, 76, 78, 79, 92, 92, 100]\n",
      "Result:   [-98, -98, -96, -92, -89, -86, -85, -83, -80, -75, -69, -65, -54, -49, -48, -45, -42, -40, -38, -36, -36, -29, -26, -23, -23, -21, -21, -20, -15, 0, 7, 10, 10, 18, 19, 21, 22, 27, 28, 31, 32, 33, 36, 38, 41, 43, 44, 45, 52, 59, 63, 64, 68, 74, 74, 74, 76, 78, 79, 92, 92, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "\t1.  [-79, -61, -56, -51, -32, -9, 12, 34, 93]\n",
      "\t2.  [-51, -39, -26, 6]\n",
      "Expected: [-79, -61, -56, -51, -51, -39, -32, -26, -9, 6, 12, 34, 93]\n",
      "Result:   [-79, -61, -56, -51, -51, -39, -32, -26, -9, 6, 12, 34, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "\t1.  [-91, -76, -52, -25, -22, -13, 96, 96]\n",
      "\t2.  [-73, -66]\n",
      "Expected: [-91, -76, -73, -66, -52, -25, -22, -13, 96, 96]\n",
      "Result:   [-91, -76, -73, -66, -52, -25, -22, -13, 96, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "\t1.  [-88, -66, -61, -49, -3, 28, 54, 73]\n",
      "\t2.  [-91, -36, -33, 11, 14, 64, 84, 96]\n",
      "\t3.  [-100, -100, -75, -52, -22, -17, 99]\n",
      "\t4.  [-47, -44, -39, -4, 25, 46, 49, 59, 97]\n",
      "\t5.  [-58, 14, 58]\n",
      "\t6.  [-73, -35, -34, -23, -6, 25, 60, 65, 68, 76]\n",
      "\t7.  [-97, 74, 90]\n",
      "\t8.  []\n",
      "\t9.  [-71, -15, 48, 87]\n",
      "Expected: [-100, -100, -97, -91, -88, -75, -73, -71, -66, -61, -58, -52, -49, -47, -44, -39, -36, -35, -34, -33, -23, -22, -17, -15, -6, -4, -3, 11, 14, 14, 25, 25, 28, 46, 48, 49, 54, 58, 59, 60, 64, 65, 68, 73, 74, 76, 84, 87, 90, 96, 97, 99]\n",
      "Result:   [-100, -100, -97, -91, -88, -75, -73, -71, -66, -61, -58, -52, -49, -47, -44, -39, -36, -35, -34, -33, -23, -22, -17, -15, -6, -4, -3, 11, 14, 14, 25, 25, 28, 46, 48, 49, 54, 58, 59, 60, 64, 65, 68, 73, 74, 76, 84, 87, 90, 96, 97, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "\t1.  [43, 54]\n",
      "\t2.  [-32, -16, 18, 30, 47, 61, 66]\n",
      "\t3.  [-90, 5, 98]\n",
      "\t4.  [-99, -63, 7, 28, 85]\n",
      "\t5.  [-89, -73, 36, 65]\n",
      "\t6.  [-93, -86, -76, -35, -3, 7, 42, 43, 52]\n",
      "Expected: [-99, -93, -90, -89, -86, -76, -73, -63, -35, -32, -16, -3, 5, 7, 7, 18, 28, 30, 36, 42, 43, 43, 47, 52, 54, 61, 65, 66, 85, 98]\n",
      "Result:   [-99, -93, -90, -89, -86, -76, -73, -63, -35, -32, -16, -3, 5, 7, 7, 18, 28, 30, 36, 42, 43, 43, 47, 52, 54, 61, 65, 66, 85, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  [-100, -90, -53, 25, 47, 50, 91, 94]\n",
      "Expected: [-100, -90, -53, 25, 47, 50, 91, 94]\n",
      "Result:   [-100, -90, -53, 25, 47, 50, 91, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  [-45, -42, -42, -11, -1, -1, 70, 76, 91]\n",
      "\t2.  [-91, -64, -41, -30, -29, -20, -1, 23, 45, 99]\n",
      "\t3.  []\n",
      "\t4.  [-85, -79, -45, -32, -22, 34, 36, 53, 63, 85]\n",
      "\t5.  [-88, -65, -59, -18, -11, 59]\n",
      "\t6.  [-15, 51, 75, 78]\n",
      "\t7.  [-9, 34]\n",
      "\t8.  [-37, -17, 34]\n",
      "Expected: [-91, -88, -85, -79, -65, -64, -59, -45, -45, -42, -42, -41, -37, -32, -30, -29, -22, -20, -18, -17, -15, -11, -11, -9, -1, -1, -1, 23, 34, 34, 34, 36, 45, 51, 53, 59, 63, 70, 75, 76, 78, 85, 91, 99]\n",
      "Result:   [-91, -88, -85, -79, -65, -64, -59, -45, -45, -42, -42, -41, -37, -32, -30, -29, -22, -20, -18, -17, -15, -11, -11, -9, -1, -1, -1, 23, 34, 34, 34, 36, 45, 51, 53, 59, 63, 70, 75, 76, 78, 85, 91, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [-64, -52, -47, -18, -13, -5, 23, 60, 95]\n",
      "Expected: [-64, -52, -47, -18, -13, -5, 23, 60, 95]\n",
      "Result:   [-64, -52, -47, -18, -13, -5, 23, 60, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-98, -46, 6, 10, 19]\n",
      "\t2.  [-86, -50, -45, -17, -4, 21, 32, 69, 72, 85]\n",
      "\t3.  [-1]\n",
      "\t4.  [-94, -91, -76, -66, -15, 54, 61]\n",
      "\t5.  []\n",
      "\t6.  [-56, -50, -24, 0]\n",
      "\t7.  [-60]\n",
      "\t8.  [-97, -57, -39, -21, 43, 100]\n",
      "\t9.  [-82, -69, -54, -2, 7, 48, 68, 87]\n",
      "Expected: [-98, -97, -94, -91, -86, -82, -76, -69, -66, -60, -57, -56, -54, -50, -50, -46, -45, -39, -24, -21, -17, -15, -4, -2, -1, 0, 6, 7, 10, 19, 21, 32, 43, 48, 54, 61, 68, 69, 72, 85, 87, 100]\n",
      "Result:   [-98, -97, -94, -91, -86, -82, -76, -69, -66, -60, -57, -56, -54, -50, -50, -46, -45, -39, -24, -21, -17, -15, -4, -2, -1, 0, 6, 7, 10, 19, 21, 32, 43, 48, 54, 61, 68, 69, 72, 85, 87, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  [-31, -24, 3, 4, 19, 40, 85]\n",
      "\t2.  [-64, 37]\n",
      "\t3.  [-90]\n",
      "\t4.  [-97, -90, -36, -14, -13, 67, 79]\n",
      "\t5.  [-83, -59, -34, 33, 44, 87]\n",
      "\t6.  []\n",
      "Expected: [-97, -90, -90, -83, -64, -59, -36, -34, -31, -24, -14, -13, 3, 4, 19, 33, 37, 40, 44, 67, 79, 85, 87]\n",
      "Result:   [-97, -90, -90, -83, -64, -59, -36, -34, -31, -24, -14, -13, 3, 4, 19, 33, 37, 40, 44, 67, 79, 85, 87]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "\t1.  [-87, -73, -23, 52, 88, 98]\n",
      "\t2.  [-94, -74, -45, -38, -37, -30, 25]\n",
      "\t3.  [-81, -65]\n",
      "\t4.  [-29]\n",
      "\t5.  [-62, -45, -20, 3, 26, 64]\n",
      "\t6.  [-25, 71, 93]\n",
      "\t7.  [94]\n",
      "Expected: [-94, -87, -81, -74, -73, -65, -62, -45, -45, -38, -37, -30, -29, -25, -23, -20, 3, 25, 26, 52, 64, 71, 88, 93, 94, 98]\n",
      "Result:   [-94, -87, -81, -74, -73, -65, -62, -45, -45, -38, -37, -30, -29, -25, -23, -20, 3, 25, 26, 52, 64, 71, 88, 93, 94, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-17, -9, 4, 7, 55, 73, 83]\n",
      "\t2.  [-51, -25, 66]\n",
      "\t3.  [-74, -4, 21]\n",
      "\t4.  []\n",
      "\t5.  [-94, -84, -71, -16, 27, 31, 31, 39, 49]\n",
      "\t6.  [-78, -22, -10, 9, 14]\n",
      "Expected: [-94, -84, -78, -74, -71, -51, -25, -22, -17, -16, -10, -9, -4, 4, 7, 9, 14, 21, 27, 31, 31, 39, 49, 55, 66, 73, 83]\n",
      "Result:   [-94, -84, -78, -74, -71, -51, -25, -22, -17, -16, -10, -9, -4, 4, 7, 9, 14, 21, 27, 31, 31, 39, 49, 55, 66, 73, 83]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  [-84, -76, -5, -4, 9, 25, 67, 74]\n",
      "\t2.  [-93]\n",
      "\t3.  [-91, -78, -75, -72, -36, 48, 99]\n",
      "\t4.  [-85, -28, 14]\n",
      "\t5.  [-95, -84, -71, 14, 48, 66, 72]\n",
      "\t6.  [-83, -81, 29, 63]\n",
      "\t7.  [-50, -32, 14, 56]\n",
      "\t8.  [-59, -24, -22, 17]\n",
      "Expected: [-95, -93, -91, -85, -84, -84, -83, -81, -78, -76, -75, -72, -71, -59, -50, -36, -32, -28, -24, -22, -5, -4, 9, 14, 14, 14, 17, 25, 29, 48, 48, 56, 63, 66, 67, 72, 74, 99]\n",
      "Result:   [-95, -93, -91, -85, -84, -84, -83, -81, -78, -76, -75, -72, -71, -59, -50, -36, -32, -28, -24, -22, -5, -4, 9, 14, 14, 14, 17, 25, 29, 48, 48, 56, 63, 66, 67, 72, 74, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "\t1.  [-42, -34, 7]\n",
      "\t2.  [-46, -19]\n",
      "\t3.  [-53, -52, 46, 47, 79, 79, 88, 95, 97]\n",
      "\t4.  [-42, -38]\n",
      "\t5.  [-91, -47, 13, 17, 56]\n",
      "\t6.  [-95, 18, 83]\n",
      "\t7.  [-96, -21, -19, -12, 11, 21, 49, 54, 64, 98]\n",
      "\t8.  [12, 47]\n",
      "\t9.  [-40, -27, 3, 12, 79]\n",
      "Expected: [-96, -95, -91, -53, -52, -47, -46, -42, -42, -40, -38, -34, -27, -21, -19, -19, -12, 3, 7, 11, 12, 12, 13, 17, 18, 21, 46, 47, 47, 49, 54, 56, 64, 79, 79, 79, 83, 88, 95, 97, 98]\n",
      "Result:   [-96, -95, -91, -53, -52, -47, -46, -42, -42, -40, -38, -34, -27, -21, -19, -19, -12, 3, 7, 11, 12, 12, 13, 17, 18, 21, 46, 47, 47, 49, 54, 56, 64, 79, 79, 79, 83, 88, 95, 97, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(LinkedList, list, merge_sorted_lists)\n",
    "# test_merging(LinkedList, list, merge_sorted_lists,\n",
    "#             samples=1000, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja funkcyjna (Nie ma sensu dodawać. Kolejka funkcyjna to tragedia.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sposób #2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W tym sposobie wykorzystujemy kolejkę priorytetową. W kolejce umieszczamy kolejno listy odsyłaczowe z priorytetem równym wartości ich obecnie pierwszego węzła. Następnie wyciągamy z kolejki (będącej w rzeczywistości minimalnym kopcem binarnym) i dopinamy pierwszy węzeł tej listy na koniec listy wynikowej, a w liście ściągniętej z kolejki, przesuwamy początkowy wskaźnik na następny element. Jeżeli tym elementem, na który przesunęliśmy wskażnik, jest None, oznacza to, że dana lista odsyłaczowa się skończyła i już jej nie rozważamy (nie dodajemy do kolejki priorytetowej). Jeżeli natomiast lista nie jest jeszcze wyczerpana, wstawiamy do kolejki priorytetowej tę listę (po przesunięciu się o 1 węzeł) wraz z priorytetem, będącym wartością obecnie pierwszego węzła. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sposób ten jest nieco bardziej skomplikowany od poprzednich i algorytm działa wolniej oraz potrzebuje więcej pamięci, ze względu na umieszczenie wskaźników do wszystkich list w kolejce priorytetowej."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja obiektowa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        \n",
    "        \n",
    "class LinkedList:\n",
    "    def __init__(self, values: 'iterable' = None):\n",
    "        self.head = self.tail = None\n",
    "        self.length = 0\n",
    "        if values: self.extend(values)\n",
    "        \n",
    "    def __iter__(self):\n",
    "        curr = self.head\n",
    "        while curr:\n",
    "            yield curr.val\n",
    "            curr = curr.next\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    \n",
    "    def extend(self, values: 'iterable'):\n",
    "        if values:\n",
    "            iterator = iter(values)\n",
    "            if not self:\n",
    "                self.head = self.tail = Node(next(iterator))\n",
    "            for val in iterator:\n",
    "                self.tail.next = Node(val)\n",
    "                self.tail = self.tail.next\n",
    "            self.length += len(values)\n",
    "        \n",
    "\n",
    "class MinPriorityQueue:\n",
    "    def __init__(self):\n",
    "        self._heap = []\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self._heap)\n",
    "        \n",
    "    def insert(self, priority: int, val: object):\n",
    "        if not isinstance(priority, int):\n",
    "            raise TypeError(f\"priority must be 'int', not {str(type(priority))[7:-1]}\")\n",
    "        # Add a value as the last node of our Complete Binary Tree\n",
    "        self._heap.append((priority, val))\n",
    "        # Fix heap in order to satisfy a min-heap property\n",
    "        self._heapify_up(len(self) - 1)\n",
    "        \n",
    "    # Removes the first value in a priority queue (of the lowest priority)\n",
    "    def poll(self):\n",
    "        if not self:\n",
    "            raise IndexError(f'poll from an empty {self.__class__.__name__}')\n",
    "        # Store a value to be returned\n",
    "        removed = self._heap[0][1]\n",
    "        # Place the last leaf in the root position\n",
    "        last = self._heap.pop()\n",
    "        if len(self) > 0:\n",
    "            self._heap[0] = last\n",
    "            # Fix a heap in order to stisfy a max-heap property\n",
    "            self._heapify_down(0, len(self))\n",
    "        return removed\n",
    "            \n",
    "    @staticmethod\n",
    "    def _parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def _left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def _right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def _swap(self, i, j):\n",
    "        self._heap[i], self._heap[j] = self._heap[j], self._heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0):  # O(log n)\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self._parent_idx(curr_idx)\n",
    "            if self._heap[curr_idx][0] < self._heap[parent_idx][0]:\n",
    "                self._swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        while True:\n",
    "            l = self._left_child_idx(curr_idx)\n",
    "            r = self._right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self._heap[l][0] < self._heap[curr_idx][0]: \n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self._heap[r][0] < self._heap[largest_idx][0]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self._swap(curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    \n",
    "def merge_sorted_lists(lls) -> LinkedList:\n",
    "    # Return an empty linked list if there are no input lists or the first list if there is\n",
    "    # only one linked list\n",
    "    if not lls: return LinkedList()\n",
    "    \n",
    "    # Else, if there are at least 2 lists, merge them to the one list\n",
    "    # Prepare variables for merging\n",
    "    result_ll = LinkedList([None])  # Create a sentinel node\n",
    "    result_ll_curr = result_ll.tail\n",
    "    pq = MinPriorityQueue()\n",
    "    for ll in lls:\n",
    "        # If is not empty, insert a linked list to the min priority queue\n",
    "        if ll:\n",
    "            pq.insert(ll.head.val, ll.head)\n",
    "            result_ll.length += len(ll)\n",
    "            \n",
    "    # Loop till a priority queue has more than 1 element (linked list) stored\n",
    "    while len(pq) > 1:\n",
    "        curr_ll = pq.poll()\n",
    "        result_ll_curr.next = curr_ll\n",
    "        curr_ll = curr_ll.next\n",
    "        result_ll_curr = result_ll_curr.next\n",
    "        # If there is still some remaining part of the current linked list, add it to the queue\n",
    "        if curr_ll:\n",
    "            pq.insert(curr_ll.val, curr_ll)\n",
    "            \n",
    "    # If there is still something remaining in the priority queue, link this list to the result\n",
    "    if pq:\n",
    "        result_ll_curr.next = pq.poll()\n",
    "    \n",
    "    # If a loop is finished, remove a sentinel node and return a result linked list\n",
    "    result_ll.head = result_ll.head.next\n",
    "    return result_ll"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (LinkedList, merge_sorted_lists, {\n",
    "    'merge_sorted_lists': merge_sorted_lists,\n",
    "    'MinPriorityQueue': MinPriorityQueue,\n",
    "    'LinkedList': LinkedList,\n",
    "    'Node': Node\n",
    "})\n",
    "algo_data['(Sposób #2) Z kolejką priorytetową obiektowo'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "\t1.  [-87, -66, -35, -11, -7, 27, 58, 70, 81, 99]\n",
      "\t2.  [-86, -84, -69, -33, -30, -7, -2, 90]\n",
      "Expected: [-87, -86, -84, -69, -66, -35, -33, -30, -11, -7, -7, -2, 27, 58, 70, 81, 90, 99]\n",
      "Result:   [-87, -86, -84, -69, -66, -35, -33, -30, -11, -7, -7, -2, 27, 58, 70, 81, 90, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [-84, -23, -8, -2, 16, 27, 27, 40, 70, 84]\n",
      "\t2.  [-86, -48, -45, -35, -24, 5, 20, 25, 63, 82]\n",
      "\t3.  [-82, 71]\n",
      "\t4.  [-88, -67, -61, -49, -36, 11, 21, 38, 67]\n",
      "\t5.  [-80, -72, -70, -67, 5, 21, 57, 80]\n",
      "Expected: [-88, -86, -84, -82, -80, -72, -70, -67, -67, -61, -49, -48, -45, -36, -35, -24, -23, -8, -2, 5, 5, 11, 16, 20, 21, 21, 25, 27, 27, 38, 40, 57, 63, 67, 70, 71, 80, 82, 84]\n",
      "Result:   [-88, -86, -84, -82, -80, -72, -70, -67, -67, -61, -49, -48, -45, -36, -35, -24, -23, -8, -2, 5, 5, 11, 16, 20, 21, 21, 25, 27, 27, 38, 40, 57, 63, 67, 70, 71, 80, 82, 84]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "\t1.  [-98, -77, -66, -56, -55, -11, 17, 36, 51, 82]\n",
      "\t2.  [-37, -34, 7, 29, 79, 80, 94]\n",
      "\t3.  [-84, 27]\n",
      "\t4.  [-41, -8, 29, 40, 52, 71]\n",
      "\t5.  [-97, 74, 91]\n",
      "\t6.  [-62, -37, 21]\n",
      "\t7.  [-90, -84, -15, 0, 34, 57, 59, 62, 80, 85]\n",
      "\t8.  [-61, -55, -52, -52, 34, 37, 90]\n",
      "\t9.  []\n",
      "Expected: [-98, -97, -90, -84, -84, -77, -66, -62, -61, -56, -55, -55, -52, -52, -41, -37, -37, -34, -15, -11, -8, 0, 7, 17, 21, 27, 29, 29, 34, 34, 36, 37, 40, 51, 52, 57, 59, 62, 71, 74, 79, 80, 80, 82, 85, 90, 91, 94]\n",
      "Result:   [-98, -97, -90, -84, -84, -77, -66, -62, -61, -56, -55, -55, -52, -52, -41, -37, -37, -34, -15, -11, -8, 0, 7, 17, 21, 27, 29, 29, 34, 34, 36, 37, 40, 51, 52, 57, 59, 62, 71, 74, 79, 80, 80, 82, 85, 90, 91, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "\t1.  [-97, -93, 15, 45]\n",
      "\t2.  [-50, -1, 8, 73]\n",
      "Expected: [-97, -93, -50, -1, 8, 15, 45, 73]\n",
      "Result:   [-97, -93, -50, -1, 8, 15, 45, 73]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "\t1.  [-71, -65, -60, -27, 12, 32, 45, 65, 78]\n",
      "\t2.  [-100, -99, -93, -30, -4, 9, 25, 29, 48, 68]\n",
      "\t3.  [-81, -12, -5, 0, 34, 46, 62, 75]\n",
      "\t4.  [-86, -24, -23, 32]\n",
      "Expected: [-100, -99, -93, -86, -81, -71, -65, -60, -30, -27, -24, -23, -12, -5, -4, 0, 9, 12, 25, 29, 32, 32, 34, 45, 46, 48, 62, 65, 68, 75, 78]\n",
      "Result:   [-100, -99, -93, -86, -81, -71, -65, -60, -30, -27, -24, -23, -12, -5, -4, 0, 9, 12, 25, 29, 32, 32, 34, 45, 46, 48, 62, 65, 68, 75, 78]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [-76, -37, 27, 32, 58, 81]\n",
      "\t3.  [49]\n",
      "\t4.  [-86, -61, -20, -7, 4, 11, 12]\n",
      "\t5.  [-96, -85, -23, -3, 40, 93]\n",
      "\t6.  [-84, -25, 7, 70, 73, 90]\n",
      "\t7.  [-98, -91, -73, -37, -17, 18, 21, 44]\n",
      "Expected: [-98, -96, -91, -86, -85, -84, -76, -73, -61, -37, -37, -25, -23, -20, -17, -7, -3, 4, 7, 11, 12, 18, 21, 27, 32, 40, 44, 49, 58, 70, 73, 81, 90, 93]\n",
      "Result:   [-98, -96, -91, -86, -85, -84, -76, -73, -61, -37, -37, -25, -23, -20, -17, -7, -3, 4, 7, 11, 12, 18, 21, 27, 32, 40, 44, 49, 58, 70, 73, 81, 90, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "\t1.  [-77, 68]\n",
      "\t2.  [-79, -43, -16, -3, 5, 9, 32, 95, 100]\n",
      "\t3.  [-28, 59, 70, 76]\n",
      "\t4.  [-23, -9, 5, 82]\n",
      "\t5.  [-48, 32]\n",
      "\t6.  [47]\n",
      "\t7.  []\n",
      "\t8.  [-97]\n",
      "\t9.  [49]\n",
      "\t10.  [-78, -66, -59, -2, 16, 23, 45, 54, 65, 78]\n",
      "Expected: [-97, -79, -78, -77, -66, -59, -48, -43, -28, -23, -16, -9, -3, -2, 5, 5, 9, 16, 23, 32, 32, 45, 47, 49, 54, 59, 65, 68, 70, 76, 78, 82, 95, 100]\n",
      "Result:   [-97, -79, -78, -77, -66, -59, -48, -43, -28, -23, -16, -9, -3, -2, 5, 5, 9, 16, 23, 32, 32, 45, 47, 49, 54, 59, 65, 68, 70, 76, 78, 82, 95, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "\t1.  [-82, -76, 1]\n",
      "\t2.  []\n",
      "\t3.  [-39, -35]\n",
      "\t4.  [-65, 14, 53]\n",
      "\t5.  [-91, -88, -87, 38, 58, 60, 96]\n",
      "\t6.  [29, 34, 39, 58, 70, 88]\n",
      "\t7.  [-61, -41, -24, 61]\n",
      "\t8.  [-96, -90, 37, 59]\n",
      "\t9.  [-78, -65, -63, -57, -48, -38, -34, -21, 9, 70]\n",
      "Expected: [-96, -91, -90, -88, -87, -82, -78, -76, -65, -65, -63, -61, -57, -48, -41, -39, -38, -35, -34, -24, -21, 1, 9, 14, 29, 34, 37, 38, 39, 53, 58, 58, 59, 60, 61, 70, 70, 88, 96]\n",
      "Result:   [-96, -91, -90, -88, -87, -82, -78, -76, -65, -65, -63, -61, -57, -48, -41, -39, -38, -35, -34, -24, -21, 1, 9, 14, 29, 34, 37, 38, 39, 53, 58, 58, 59, 60, 61, 70, 70, 88, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "\t1.  [-67, -64, -52, 2]\n",
      "\t2.  [0]\n",
      "\t3.  [-97, -87, -81, -67, -31, -10, 100]\n",
      "\t4.  []\n",
      "Expected: [-97, -87, -81, -67, -67, -64, -52, -31, -10, 0, 2, 100]\n",
      "Result:   [-97, -87, -81, -67, -67, -64, -52, -31, -10, 0, 2, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  [-68, -50, -49, 33, 64, 71]\n",
      "\t2.  [-55]\n",
      "\t3.  [-39, -36, 1, 3, 10, 30, 56, 73, 90, 90]\n",
      "\t4.  [-34, -26, -21, -16, -10, 14, 30, 69, 79]\n",
      "Expected: [-68, -55, -50, -49, -39, -36, -34, -26, -21, -16, -10, 1, 3, 10, 14, 30, 30, 33, 56, 64, 69, 71, 73, 79, 90, 90]\n",
      "Result:   [-68, -55, -50, -49, -39, -36, -34, -26, -21, -16, -10, 1, 3, 10, 14, 30, 30, 33, 56, 64, 69, 71, 73, 79, 90, 90]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  [15, 35, 89]\n",
      "\t2.  [-91, -46, -37, 9, 38, 41]\n",
      "\t3.  [-74, -59, -55, -17, 2, 48, 60, 77]\n",
      "\t4.  [-87, -76, -55, -46, 2, 77]\n",
      "\t5.  [-87, -1, 41]\n",
      "\t6.  [-19, -6, 14, 84, 94]\n",
      "\t7.  [-91, -68, -53, -52, -34, -32, 11, 36, 79, 87]\n",
      "Expected: [-91, -91, -87, -87, -76, -74, -68, -59, -55, -55, -53, -52, -46, -46, -37, -34, -32, -19, -17, -6, -1, 2, 2, 9, 11, 14, 15, 35, 36, 38, 41, 41, 48, 60, 77, 77, 79, 84, 87, 89, 94]\n",
      "Result:   [-91, -91, -87, -87, -76, -74, -68, -59, -55, -55, -53, -52, -46, -46, -37, -34, -32, -19, -17, -6, -1, 2, 2, 9, 11, 14, 15, 35, 36, 38, 41, 41, 48, 60, 77, 77, 79, 84, 87, 89, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [-19]\n",
      "\t2.  [-88, -77, -48, -27, -2, 60, 90]\n",
      "\t3.  []\n",
      "\t4.  [21, 27]\n",
      "\t5.  [-13, 14, 97, 100]\n",
      "\t6.  [18, 23, 36, 39, 47, 54, 59, 60, 75]\n",
      "Expected: [-88, -77, -48, -27, -19, -13, -2, 14, 18, 21, 23, 27, 36, 39, 47, 54, 59, 60, 60, 75, 90, 97, 100]\n",
      "Result:   [-88, -77, -48, -27, -19, -13, -2, 14, 18, 21, 23, 27, 36, 39, 47, 54, 59, 60, 60, 75, 90, 97, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-77, -75, -11, 92]\n",
      "Expected: [-77, -75, -11, 92]\n",
      "Result:   [-77, -75, -11, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  [-99, -90, -60, -51, 10, 36, 62, 86, 96]\n",
      "\t2.  [-72, -70, 37]\n",
      "\t3.  [-93, -44, -6, 33, 78, 86]\n",
      "\t4.  [-48, -35, -22, -19, 11, 44, 78]\n",
      "\t5.  [-71, 50, 64]\n",
      "Expected: [-99, -93, -90, -72, -71, -70, -60, -51, -48, -44, -35, -22, -19, -6, 10, 11, 33, 36, 37, 44, 50, 62, 64, 78, 78, 86, 86, 96]\n",
      "Result:   [-99, -93, -90, -72, -71, -70, -60, -51, -48, -44, -35, -22, -19, -6, 10, 11, 33, 36, 37, 44, 50, 62, 64, 78, 78, 86, 86, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "\t1.  [-76, -24]\n",
      "\t2.  [-71, -58, -42, -42, -32, -5, 1, 6, 16, 53]\n",
      "\t3.  [-88, -12, 14, 60, 62, 68, 72]\n",
      "\t4.  [-99, -69, -66, -27, 58, 86, 92]\n",
      "\t5.  [-46]\n",
      "Expected: [-99, -88, -76, -71, -69, -66, -58, -46, -42, -42, -32, -27, -24, -12, -5, 1, 6, 14, 16, 53, 58, 60, 62, 68, 72, 86, 92]\n",
      "Result:   [-99, -88, -76, -71, -69, -66, -58, -46, -42, -42, -32, -27, -24, -12, -5, 1, 6, 14, 16, 53, 58, 60, 62, 68, 72, 86, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-68, -48, -36, 76]\n",
      "\t2.  [-94, -79, -66, -22, 21, 30, 64, 80, 84]\n",
      "\t3.  []\n",
      "\t4.  [-63, -34, -26, -24, 17, 19, 22, 66, 96]\n",
      "\t5.  [-41, -24, -20, 93]\n",
      "Expected: [-94, -79, -68, -66, -63, -48, -41, -36, -34, -26, -24, -24, -22, -20, 17, 19, 21, 22, 30, 64, 66, 76, 80, 84, 93, 96]\n",
      "Result:   [-94, -79, -68, -66, -63, -48, -41, -36, -34, -26, -24, -24, -22, -20, 17, 19, 21, 22, 30, 64, 66, 76, 80, 84, 93, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "\t1.  [81]\n",
      "Expected: [81]\n",
      "Result:   [81]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  [-89, -40, -14]\n",
      "\t2.  [-95, -73, -60, -59, -8, 11, 39, 40, 66, 84]\n",
      "\t3.  []\n",
      "\t4.  [-97, -76, -69, -33, -4, 2, 38, 47, 83, 95]\n",
      "\t5.  [-90, -82, -48, 39, 75, 93, 94]\n",
      "\t6.  [-26, 66, 79]\n",
      "\t7.  [84]\n",
      "Expected: [-97, -95, -90, -89, -82, -76, -73, -69, -60, -59, -48, -40, -33, -26, -14, -8, -4, 2, 11, 38, 39, 39, 40, 47, 66, 66, 75, 79, 83, 84, 84, 93, 94, 95]\n",
      "Result:   [-97, -95, -90, -89, -82, -76, -73, -69, -60, -59, -48, -40, -33, -26, -14, -8, -4, 2, 11, 38, 39, 39, 40, 47, 66, 66, 75, 79, 83, 84, 84, 93, 94, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "\t1.  [-19, 18, 63, 71, 98]\n",
      "\t2.  []\n",
      "\t3.  [-7, 0]\n",
      "Expected: [-19, -7, 0, 18, 63, 71, 98]\n",
      "Result:   [-19, -7, 0, 18, 63, 71, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(LinkedList, list, merge_sorted_lists)\n",
    "# test_merging(LinkedList, list, merge_sorted_lists,\n",
    "#             samples=100, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja funkcyjna "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def create_linked_list(values: 'iterable' = None) -> 'linked list head (sentinel)':\n",
    "    head = Node()  # A sentinel node\n",
    "    if not values: return head\n",
    "    head.next = curr = Node(values[0])\n",
    "    for i in range(1, len(values)):\n",
    "        curr.next = Node(values[i])\n",
    "        curr = curr.next\n",
    "    return head\n",
    "\n",
    "\n",
    "_left = lambda i: 2 * i + 1\n",
    "_right = lambda i: 2 * i + 2\n",
    "_parent = lambda i: (i - 1) // 2\n",
    "        \n",
    "        \n",
    "def insert_to_min_priority_queue(queue: list, priority: int, val: object):\n",
    "    if not isinstance(priority, int):\n",
    "        raise TypeError(f\"priority must be 'int', not {str(type(priority))[7:-1]}\")\n",
    "    # Add a value as the last node of our Complete Binary Tree\n",
    "    queue.append((priority, val))\n",
    "    # Fix heap in order to satisfy a max-heap property\n",
    "    _heapify_up(queue, len(queue) - 1)\n",
    "    \n",
    "    \n",
    "def poll_from_min_priority_queue(queue: list) -> object:\n",
    "    if not queue:\n",
    "        raise IndexError(f'poll from an empty Priority Queue')\n",
    "    # Store a value to be returned\n",
    "    removed = queue[0][1]\n",
    "    # Place the last leaf in the root position\n",
    "    last = queue.pop()\n",
    "    if queue:\n",
    "        queue[0] = last\n",
    "        # Fix a heap in order to stisfy a max-heap property\n",
    "        _heapify_down(queue, 0, len(queue))\n",
    "    return removed\n",
    "\n",
    "    \n",
    "def _swap(queue: list, i, j):\n",
    "    queue[i], queue[j] = queue[j], queue[i]\n",
    "    \n",
    "    \n",
    "def _heapify_up(queue: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index' = 0):\n",
    "    while curr_idx > end_idx:\n",
    "        parent_idx = _parent(curr_idx)\n",
    "        if queue[curr_idx][0] < queue[parent_idx][0]:\n",
    "            _swap(queue, curr_idx, parent_idx)\n",
    "        curr_idx = parent_idx\n",
    "            \n",
    "    \n",
    "def _heapify_down(queue: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index'):\n",
    "    while True:\n",
    "        i = _left(curr_idx)\n",
    "        j = _right(curr_idx)\n",
    "        k = curr_idx\n",
    "        \n",
    "        if i < end_idx:\n",
    "            if queue[i][0] < queue[k][0]:\n",
    "                k = i\n",
    "            if j < end_idx and queue[j][0] < queue[k][0]:\n",
    "                k = j\n",
    "                \n",
    "        if k == curr_idx: return\n",
    "        # Swap the current with the largest child\n",
    "        queue[curr_idx], queue[k] = queue[k], queue[curr_idx]\n",
    "        curr_idx = k\n",
    "        \n",
    "        \n",
    "def merge_sorted_lists(lls) -> 'linked list head (sentinel)':\n",
    "    # Return an empty linked list (sentinel node) if there is no linked list in a lls iterable\n",
    "    if not lls: return Node()\n",
    "    \n",
    "    # Else, if there are at least 2 lists, merge them to the one list\n",
    "    # Prepare variables for merging\n",
    "    result_ll = Node()\n",
    "    result_curr = result_ll\n",
    "    pq = []\n",
    "    for ll_head in lls:\n",
    "        # If is not empty, insert a linked list to the min priority queue\n",
    "        if ll_head.next:\n",
    "            insert_to_min_priority_queue(pq, ll_head.next.val, ll_head.next)\n",
    "            \n",
    "    # Loop till a priority queue has more than 1 element (linked list) stored\n",
    "    while len(pq) > 1:\n",
    "        curr_head = poll_from_min_priority_queue(pq)\n",
    "        result_curr.next = curr_head\n",
    "        curr_head = curr_head.next\n",
    "        result_curr = result_curr.next\n",
    "        # If there is still some remaining part of the current linked list, add it to the queue\n",
    "        if curr_head:\n",
    "            insert_to_min_priority_queue(pq, curr_head.val, curr_head)\n",
    "            \n",
    "    # If there is still something remaining in the priority queue, link this list to the result\n",
    "    if pq:\n",
    "        result_curr.next = poll_from_min_priority_queue(pq)\n",
    "\n",
    "    return result_ll"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja pomocnicza, konwertująca listę odsyłaczową do listy Pythonowej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linked_list_to_list(ll_head: 'linked list head (sentinel)') -> list:\n",
    "    result = []\n",
    "    curr = ll_head.next\n",
    "    while curr:\n",
    "        result.append(curr.val)\n",
    "        curr = curr.next\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (create_linked_list, merge_sorted_lists, {\n",
    "    'create_linked_list': create_linked_list,\n",
    "    'Node': Node,\n",
    "    '_left': _left,\n",
    "    '_right': _right,\n",
    "    '_parent': _parent,\n",
    "    'insert_to_min_priority_queue': insert_to_min_priority_queue,\n",
    "    'poll_from_min_priority_queue': poll_from_min_priority_queue,\n",
    "    '_swap': _swap,\n",
    "    '_heapify_up': _heapify_up,\n",
    "    '_heapify_down': _heapify_down,\n",
    "    'merge_sorted_lists': merge_sorted_lists,\n",
    "    'linked_list_to_list': linked_list_to_list,\n",
    "})\n",
    "algo_data['(Sposób #2) Z kolejką priorytetową funkcyjnie'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [9, 97]\n",
      "\t2.  []\n",
      "Expected: [9, 97]\n",
      "Result:   [9, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "\t1.  [-97, -51, -51, -41, -31, -11, 19, 73, 94, 98]\n",
      "\t2.  []\n",
      "\t3.  [-85, -66, -13, -9, 38, 39, 46, 70]\n",
      "\t4.  [-35, 14, 84]\n",
      "\t5.  [-85, -26, 94]\n",
      "\t6.  [-93, -80, -53, -51, 77, 98]\n",
      "\t7.  [-95, -77, -68, -64, -52, -7, 57, 83, 92]\n",
      "Expected: [-97, -95, -93, -85, -85, -80, -77, -68, -66, -64, -53, -52, -51, -51, -51, -41, -35, -31, -26, -13, -11, -9, -7, 14, 19, 38, 39, 46, 57, 70, 73, 77, 83, 84, 92, 94, 94, 98, 98]\n",
      "Result:   [-97, -95, -93, -85, -85, -80, -77, -68, -66, -64, -53, -52, -51, -51, -51, -41, -35, -31, -26, -13, -11, -9, -7, 14, 19, 38, 39, 46, 57, 70, 73, 77, 83, 84, 92, 94, 94, 98, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "\t1.  [-49, 8, 9, 31]\n",
      "\t2.  [-86, -22, 27, 65, 84, 99]\n",
      "Expected: [-86, -49, -22, 8, 9, 27, 31, 65, 84, 99]\n",
      "Result:   [-86, -49, -22, 8, 9, 27, 31, 65, 84, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "\t1.  [-79]\n",
      "\t2.  [-91, -17, 19, 48, 49, 82]\n",
      "\t3.  [7, 33]\n",
      "Expected: [-91, -79, -17, 7, 19, 33, 48, 49, 82]\n",
      "Result:   [-91, -79, -17, 7, 19, 33, 48, 49, 82]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "\t1.  [-69, -30, -16, -6]\n",
      "\t2.  [-77, -63, -33, -30, -9, 0, 67, 79]\n",
      "\t3.  [-78, -77, -76, -50, -20, 45]\n",
      "\t4.  [-80, -78, -69, -15, -5, 31, 49, 90, 95]\n",
      "\t5.  [-84, 28, 37, 88]\n",
      "\t6.  [-95, -57, -11, 3, 9, 68]\n",
      "\t7.  [-100, -47, -47, -36, -34, -11, 26]\n",
      "\t8.  [-66, -51]\n",
      "\t9.  [-96, -59, -58, 4, 6, 55]\n",
      "\t10.  [-70, -39, -28, -26, 25, 58, 62, 83, 91, 92]\n",
      "Expected: [-100, -96, -95, -84, -80, -78, -78, -77, -77, -76, -70, -69, -69, -66, -63, -59, -58, -57, -51, -50, -47, -47, -39, -36, -34, -33, -30, -30, -28, -26, -20, -16, -15, -11, -11, -9, -6, -5, 0, 3, 4, 6, 9, 25, 26, 28, 31, 37, 45, 49, 55, 58, 62, 67, 68, 79, 83, 88, 90, 91, 92, 95]\n",
      "Result:   [-100, -96, -95, -84, -80, -78, -78, -77, -77, -76, -70, -69, -69, -66, -63, -59, -58, -57, -51, -50, -47, -47, -39, -36, -34, -33, -30, -30, -28, -26, -20, -16, -15, -11, -11, -9, -6, -5, 0, 3, 4, 6, 9, 25, 26, 28, 31, 37, 45, 49, 55, 58, 62, 67, 68, 79, 83, 88, 90, 91, 92, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "\t1.  [-90, -65, -59, -29, 31, 54, 73, 75, 76]\n",
      "\t2.  [-97, -38, -12, 7, 56, 58, 63, 76, 89]\n",
      "\t3.  [-53, 31, 66]\n",
      "\t4.  [-63, -43, -11, 7, 9, 10, 15, 29, 64, 65]\n",
      "\t5.  [-99, -5, 45, 50, 60, 63, 64, 85]\n",
      "Expected: [-99, -97, -90, -65, -63, -59, -53, -43, -38, -29, -12, -11, -5, 7, 7, 9, 10, 15, 29, 31, 31, 45, 50, 54, 56, 58, 60, 63, 63, 64, 64, 65, 66, 73, 75, 76, 76, 85, 89]\n",
      "Result:   [-99, -97, -90, -65, -63, -59, -53, -43, -38, -29, -12, -11, -5, 7, 7, 9, 10, 15, 29, 31, 31, 45, 50, 54, 56, 58, 60, 63, 63, 64, 64, 65, 66, 73, 75, 76, 76, 85, 89]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "\t1.  [55]\n",
      "\t2.  [-27, -9, 61]\n",
      "\t3.  [-99, -94, -94, 4, 35, 76]\n",
      "\t4.  [3]\n",
      "\t5.  [-38, -31, -23, 53, 56, 61, 67, 81]\n",
      "\t6.  [-25, -2, 56]\n",
      "\t7.  [-53]\n",
      "\t8.  [-57, -46, -40, -13, 37]\n",
      "Expected: [-99, -94, -94, -57, -53, -46, -40, -38, -31, -27, -25, -23, -13, -9, -2, 3, 4, 35, 37, 53, 55, 56, 56, 61, 61, 67, 76, 81]\n",
      "Result:   [-99, -94, -94, -57, -53, -46, -40, -38, -31, -27, -25, -23, -13, -9, -2, 3, 4, 35, 37, 53, 55, 56, 56, 61, 61, 67, 76, 81]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [-61, -47, -34, -18, 28, 81, 82, 89]\n",
      "\t3.  [-74, -69, -55, -41, 9, 68, 80]\n",
      "\t4.  [-20, 35, 56, 84, 85, 96]\n",
      "Expected: [-74, -69, -61, -55, -47, -41, -34, -20, -18, 9, 28, 35, 56, 68, 80, 81, 82, 84, 85, 89, 96]\n",
      "Result:   [-74, -69, -61, -55, -47, -41, -34, -20, -18, 9, 28, 35, 56, 68, 80, 81, 82, 84, 85, 89, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  [-34, -10, 29, 64, 95]\n",
      "\t2.  []\n",
      "\t3.  [-97, -81, -80, -55, -51, -50, -25, 6, 22, 99]\n",
      "\t4.  [-83, -60, -54, -41, -22, 17, 48, 77, 86, 96]\n",
      "\t5.  [-80, -53, -12, 21, 86]\n",
      "\t6.  [5, 37]\n",
      "\t7.  [-98, -78, -15, 18, 43, 50, 88, 90]\n",
      "\t8.  [-62, -61, 14, 31, 40, 94]\n",
      "\t9.  [-84, 14, 45, 55]\n",
      "\t10.  [-75, -59, -55, -47, 44]\n",
      "Expected: [-98, -97, -84, -83, -81, -80, -80, -78, -75, -62, -61, -60, -59, -55, -55, -54, -53, -51, -50, -47, -41, -34, -25, -22, -15, -12, -10, 5, 6, 14, 14, 17, 18, 21, 22, 29, 31, 37, 40, 43, 44, 45, 48, 50, 55, 64, 77, 86, 86, 88, 90, 94, 95, 96, 99]\n",
      "Result:   [-98, -97, -84, -83, -81, -80, -80, -78, -75, -62, -61, -60, -59, -55, -55, -54, -53, -51, -50, -47, -41, -34, -25, -22, -15, -12, -10, 5, 6, 14, 14, 17, 18, 21, 22, 29, 31, 37, 40, 43, 44, 45, 48, 50, 55, 64, 77, 86, 86, 88, 90, 94, 95, 96, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [-78, -54, -29, -22, -4, 2, 22, 24, 69, 86]\n",
      "\t2.  [-75, -51, 1, 50, 51]\n",
      "\t3.  [-76, 4]\n",
      "\t4.  [-69, -39, -14, 12, 21, 27]\n",
      "\t5.  []\n",
      "\t6.  [-53, -9, 19]\n",
      "\t7.  [-68]\n",
      "\t8.  [-70, -62, -29, -21, 41, 97]\n",
      "\t9.  [-88, 13, 64, 74]\n",
      "Expected: [-88, -78, -76, -75, -70, -69, -68, -62, -54, -53, -51, -39, -29, -29, -22, -21, -14, -9, -4, 1, 2, 4, 12, 13, 19, 21, 22, 24, 27, 41, 50, 51, 64, 69, 74, 86, 97]\n",
      "Result:   [-88, -78, -76, -75, -70, -69, -68, -62, -54, -53, -51, -39, -29, -29, -22, -21, -14, -9, -4, 1, 2, 4, 12, 13, 19, 21, 22, 24, 27, 41, 50, 51, 64, 69, 74, 86, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-75, -52, -50, -5, 49, 51, 73, 94]\n",
      "\t2.  [-74, -3, 10, 35, 48, 90]\n",
      "\t3.  [-79, -70, -69, -27, -16, -6, 28, 37, 48]\n",
      "\t4.  [-97, -76, -62, -48, -46, -45, -20, 10, 32, 45]\n",
      "\t5.  [-99, -89, -61, -57, -28, -17, 59, 66, 66, 80]\n",
      "\t6.  [-82, -24, 2, 18, 33, 38, 51]\n",
      "\t7.  [-11]\n",
      "\t8.  [5]\n",
      "\t9.  [-94, -86, -77, -38, 35, 45, 60, 61, 95, 96]\n",
      "Expected: [-99, -97, -94, -89, -86, -82, -79, -77, -76, -75, -74, -70, -69, -62, -61, -57, -52, -50, -48, -46, -45, -38, -28, -27, -24, -20, -17, -16, -11, -6, -5, -3, 2, 5, 10, 10, 18, 28, 32, 33, 35, 35, 37, 38, 45, 45, 48, 48, 49, 51, 51, 59, 60, 61, 66, 66, 73, 80, 90, 94, 95, 96]\n",
      "Result:   [-99, -97, -94, -89, -86, -82, -79, -77, -76, -75, -74, -70, -69, -62, -61, -57, -52, -50, -48, -46, -45, -38, -28, -27, -24, -20, -17, -16, -11, -6, -5, -3, 2, 5, 10, 10, 18, 28, 32, 33, 35, 35, 37, 38, 45, 45, 48, 48, 49, 51, 51, 59, 60, 61, 66, 66, 73, 80, 90, 94, 95, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  [-92, -80, -60, 26, 60, 72]\n",
      "\t2.  [-99, -38, 82, 86]\n",
      "\t3.  [-89, -48, 81]\n",
      "\t4.  [-96, -89, -77, -28, -21, -8, 91]\n",
      "\t5.  [-87, 50]\n",
      "Expected: [-99, -96, -92, -89, -89, -87, -80, -77, -60, -48, -38, -28, -21, -8, 26, 50, 60, 72, 81, 82, 86, 91]\n",
      "Result:   [-99, -96, -92, -89, -89, -87, -80, -77, -60, -48, -38, -28, -21, -8, 26, 50, 60, 72, 81, 82, 86, 91]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "\t1.  [-53, -46, 77]\n",
      "\t2.  [-27]\n",
      "\t3.  [-24, -20, -20, 32, 38, 39, 81]\n",
      "\t4.  [-70, -38, -27, 7, 11, 16, 46, 58, 92, 99]\n",
      "\t5.  [-15]\n",
      "\t6.  [-100, -71, -54, -25, -15, 60, 65, 67, 77, 89]\n",
      "\t7.  [-48, -36, -13, 30, 54]\n",
      "\t8.  [-78, -10, 22, 28, 48]\n",
      "\t9.  [-88, -61, -13, -2, 7, 28, 81]\n",
      "Expected: [-100, -88, -78, -71, -70, -61, -54, -53, -48, -46, -38, -36, -27, -27, -25, -24, -20, -20, -15, -15, -13, -13, -10, -2, 7, 7, 11, 16, 22, 28, 28, 30, 32, 38, 39, 46, 48, 54, 58, 60, 65, 67, 77, 77, 81, 81, 89, 92, 99]\n",
      "Result:   [-100, -88, -78, -71, -70, -61, -54, -53, -48, -46, -38, -36, -27, -27, -25, -24, -20, -20, -15, -15, -13, -13, -10, -2, 7, 7, 11, 16, 22, 28, 28, 30, 32, 38, 39, 46, 48, 54, 58, 60, 65, 67, 77, 77, 81, 81, 89, 92, 99]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-34, -12, 68, 85]\n",
      "\t2.  [-81]\n",
      "\t3.  [-100, -12, -9, 9, 60]\n",
      "Expected: [-100, -81, -34, -12, -12, -9, 9, 60, 68, 85]\n",
      "Result:   [-100, -81, -34, -12, -12, -9, 9, 60, 68, 85]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [93]\n",
      "\t3.  [-4, 13, 57, 80]\n",
      "\t4.  [-8, -5, 10, 38, 45, 65, 69, 84]\n",
      "\t5.  [-48, 2, 10, 10, 54, 66, 69]\n",
      "Expected: [-48, -8, -5, -4, 2, 10, 10, 10, 13, 38, 45, 54, 57, 65, 66, 69, 69, 80, 84, 93]\n",
      "Result:   [-48, -8, -5, -4, 2, 10, 10, 10, 13, 38, 45, 54, 57, 65, 66, 69, 69, 80, 84, 93]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  [-33, -21, -15, 16, 33, 33, 37, 56, 96]\n",
      "\t2.  [-88, -67, -64, -64, -61, -60, -36, -27, 16, 25]\n",
      "\t3.  [-71, -57, -37, -9, 32, 35, 41, 67, 95]\n",
      "\t4.  [-100, -90, -67, -56, -33, -1]\n",
      "\t5.  [-64, -9, 4, 95, 97]\n",
      "\t6.  [-92, -72, -40, -31, -5, 14, 51, 84]\n",
      "\t7.  [-32, 1, 37, 54, 55, 69, 90]\n",
      "\t8.  [-54, -39, -38, 16]\n",
      "Expected: [-100, -92, -90, -88, -72, -71, -67, -67, -64, -64, -64, -61, -60, -57, -56, -54, -40, -39, -38, -37, -36, -33, -33, -32, -31, -27, -21, -15, -9, -9, -5, -1, 1, 4, 14, 16, 16, 16, 25, 32, 33, 33, 35, 37, 37, 41, 51, 54, 55, 56, 67, 69, 84, 90, 95, 95, 96, 97]\n",
      "Result:   [-100, -92, -90, -88, -72, -71, -67, -67, -64, -64, -64, -61, -60, -57, -56, -54, -40, -39, -38, -37, -36, -33, -33, -32, -31, -27, -21, -15, -9, -9, -5, -1, 1, 4, 14, 16, 16, 16, 25, 32, 33, 33, 35, 37, 37, 41, 51, 54, 55, 56, 67, 69, 84, 90, 95, 95, 96, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(create_linked_list, linked_list_to_list, merge_sorted_lists)\n",
    "# test_merging(create_linked_list, linked_list_to_list, merge_sorted_lists,\n",
    "#             samples=100, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sposób #3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sposób podobny do #1, ale tym razem łączymy zawsze 2 najkrótsze pod względem liczby węzłów listy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementacja funkcyjna"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MinPriorityQueue:\n",
    "    def __init__(self):\n",
    "        self._heap = []\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self._heap)\n",
    "        \n",
    "    def insert(self, priority: int, val: object):\n",
    "        if not isinstance(priority, int):\n",
    "            raise TypeError(f\"priority must be 'int', not {str(type(priority))[7:-1]}\")\n",
    "        # Add a value as the last node of our Complete Binary Tree\n",
    "        self._heap.append((priority, val))\n",
    "        # Fix heap in order to satisfy a min-heap property\n",
    "        self._heapify_up(len(self) - 1)\n",
    "        \n",
    "    # Removes the first value in a priority queue (of the lowest priority)\n",
    "    def poll(self):\n",
    "        if not self:\n",
    "            raise IndexError(f'poll from an empty {self.__class__.__name__}')\n",
    "        # Store a value to be returned\n",
    "        removed = self._heap[0]\n",
    "        # Place the last leaf in the root position\n",
    "        last = self._heap.pop()\n",
    "        if len(self) > 0:\n",
    "            self._heap[0] = last\n",
    "            # Fix a heap in order to stisfy a max-heap property\n",
    "            self._heapify_down(0, len(self))\n",
    "        return removed\n",
    "            \n",
    "    @staticmethod\n",
    "    def _parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def _left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def _right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def _swap(self, i, j):\n",
    "        self._heap[i], self._heap[j] = self._heap[j], self._heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0):  # O(log n)\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self._parent_idx(curr_idx)\n",
    "            if self._heap[curr_idx][0] < self._heap[parent_idx][0]:\n",
    "                self._swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        while True:\n",
    "            l = self._left_child_idx(curr_idx)\n",
    "            r = self._right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self._heap[l][0] < self._heap[curr_idx][0]: \n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self._heap[r][0] < self._heap[largest_idx][0]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self._swap(curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "                \n",
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.next = None\n",
    "        self.val = val\n",
    "\n",
    "\n",
    "def get_length(head):\n",
    "    length = 0\n",
    "    curr = head.next\n",
    "    while curr:\n",
    "        length += 1\n",
    "        curr = curr.next\n",
    "    return length\n",
    "\n",
    "\n",
    "def _merge(head1, head2):\n",
    "    curr1 = head1.next\n",
    "    curr2 = head2.next\n",
    "    head = tail = Node(None)\n",
    "\n",
    "    while curr1 and curr2:\n",
    "        if curr1.val < curr2.val:\n",
    "            tail.next = curr1\n",
    "            curr1 = curr1.next\n",
    "        else:\n",
    "            tail.next = curr2\n",
    "            curr2 = curr2.next\n",
    "        tail = tail.next\n",
    "\n",
    "    if curr1: tail.next = curr1\n",
    "    else:     tail.next = curr2\n",
    "\n",
    "    return head\n",
    "\n",
    "    \n",
    "def merge_lists(L):\n",
    "    n = len(L)\n",
    "    if not L: return Node()\n",
    "    if n == 1: return L[0]\n",
    "    # Get length of each list and add this list with its length\n",
    "    # as a priority to the minimum priority queue\n",
    "    pq = MinPriorityQueue()\n",
    "    i = 0\n",
    "    while i < n:\n",
    "        pq.insert(get_length(L[i]), L[i])\n",
    "        i += 1\n",
    "    # In a loop, merge lists of the lowest length together and add\n",
    "    # a resulting list back to the priority queue\n",
    "    while len(pq) > 1:\n",
    "        length1, head1 = pq.poll()\n",
    "        length2, head2 = pq.poll()\n",
    "        new_head = _merge(head1, head2)\n",
    "        new_length = length1 + length2\n",
    "        if pq:\n",
    "            pq.insert(new_length, new_head)\n",
    "            i += 1\n",
    "        else:\n",
    "            return new_head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja pomocnicza, konwertująca listę odsyłaczową do listy Pythonowej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linked_list_to_list(ll_head: 'linked list head (sentinel)') -> list:\n",
    "    result = []\n",
    "    curr = ll_head.next\n",
    "    while curr:\n",
    "        result.append(curr.val)\n",
    "        curr = curr.next\n",
    "    return result\n",
    "\n",
    "def create_linked_list(values: 'iterable' = None) -> 'linked list head (sentinel)':\n",
    "    head = Node()  # A sentinel node\n",
    "    if not values: return head\n",
    "    head.next = curr = Node(values[0])\n",
    "    for i in range(1, len(values)):\n",
    "        curr.next = Node(values[i])\n",
    "        curr = curr.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Zapisujemy dane do późniejszego benchmarku (nie jest to częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = (create_linked_list, merge_lists, {\n",
    "    'Node': Node,\n",
    "    'get_length': get_length,\n",
    "    '_merge': _merge,\n",
    "    'merge_lists': merge_lists,\n",
    "    'linked_list_to_list': linked_list_to_list,\n",
    "    'create_linked_list': create_linked_list,\n",
    "    'MinPriorityQueue': MinPriorityQueue\n",
    "})\n",
    "algo_data['(Sposób #3) Z kolejką priorytetową po długości'] = data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test #1:\n",
      "Input lists:\n",
      "\t1.  [-94, -88, -83, -79, -69, -60, -55, 22, 38, 46]\n",
      "\t2.  [-83, -66, -64, -47, -37, 13, 20, 24, 32, 72]\n",
      "\t3.  [-97, -67, -45, 73, 78, 95]\n",
      "\t4.  [-57, -36, -6, 5, 34, 53, 81]\n",
      "\t5.  [-98, -98, -69, -67, -29, -25, -10, 11, 61]\n",
      "\t6.  []\n",
      "\t7.  [-73, -10, 32]\n",
      "Expected: [-98, -98, -97, -94, -88, -83, -83, -79, -73, -69, -69, -67, -67, -66, -64, -60, -57, -55, -47, -45, -37, -36, -29, -25, -10, -10, -6, 5, 11, 13, 20, 22, 24, 32, 32, 34, 38, 46, 53, 61, 72, 73, 78, 81, 95]\n",
      "Result:   [-98, -98, -97, -94, -88, -83, -83, -79, -73, -69, -69, -67, -67, -66, -64, -60, -57, -55, -47, -45, -37, -36, -29, -25, -10, -10, -6, 5, 11, 13, 20, 22, 24, 32, 32, 34, 38, 46, 53, 61, 72, 73, 78, 81, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 1/1\n",
      "\n",
      "Test #2:\n",
      "Input lists:\n",
      "\t1.  [29]\n",
      "\t2.  [-91, -74, -47, -36, 24, 56, 60, 73]\n",
      "\t3.  [-96, -54, -53, -49, -40, -27, 25, 61, 70, 74]\n",
      "\t4.  [-84, -71, -67, 45, 58, 66, 76]\n",
      "\t5.  [-85, -63, -32, -10, -8, 58, 92]\n",
      "\t6.  [-84, -70, -56, 9, 94]\n",
      "\t7.  [-47, -12, 56]\n",
      "\t8.  [-83, 3, 62, 64, 91]\n",
      "\t9.  [-89, -77, 49, 53, 66, 77, 81, 90]\n",
      "\t10.  []\n",
      "Expected: [-96, -91, -89, -85, -84, -84, -83, -77, -74, -71, -70, -67, -63, -56, -54, -53, -49, -47, -47, -40, -36, -32, -27, -12, -10, -8, 3, 9, 24, 25, 29, 45, 49, 53, 56, 56, 58, 58, 60, 61, 62, 64, 66, 66, 70, 73, 74, 76, 77, 81, 90, 91, 92, 94]\n",
      "Result:   [-96, -91, -89, -85, -84, -84, -83, -77, -74, -71, -70, -67, -63, -56, -54, -53, -49, -47, -47, -40, -36, -32, -27, -12, -10, -8, 3, 9, 24, 25, 29, 45, 49, 53, 56, 56, 58, 58, 60, 61, 62, 64, 66, 66, 70, 73, 74, 76, 77, 81, 90, 91, 92, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 2/2\n",
      "\n",
      "Test #3:\n",
      "Input lists:\n",
      "\t1.  [-15]\n",
      "\t2.  [-98, -87, -62, 33, 37, 43, 53, 76, 80]\n",
      "\t3.  [-95, 91]\n",
      "\t4.  []\n",
      "\t5.  [-33, 42]\n",
      "\t6.  [-49, -33, -19, 85]\n",
      "Expected: [-98, -95, -87, -62, -49, -33, -33, -19, -15, 33, 37, 42, 43, 53, 76, 80, 85, 91]\n",
      "Result:   [-98, -95, -87, -62, -49, -33, -33, -19, -15, 33, 37, 42, 43, 53, 76, 80, 85, 91]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 3/3\n",
      "\n",
      "Test #4:\n",
      "Input lists:\n",
      "\t1.  [68]\n",
      "\t2.  []\n",
      "\t3.  [-91]\n",
      "\t4.  []\n",
      "\t5.  [-58, -17, -16, -11, 25, 67, 87, 94]\n",
      "\t6.  [-43, 69, 84]\n",
      "\t7.  [-69, 2, 58, 59]\n",
      "Expected: [-91, -69, -58, -43, -17, -16, -11, 2, 25, 58, 59, 67, 68, 69, 84, 87, 94]\n",
      "Result:   [-91, -69, -58, -43, -17, -16, -11, 2, 25, 58, 59, 67, 68, 69, 84, 87, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 4/4\n",
      "\n",
      "Test #5:\n",
      "Input lists:\n",
      "\t1.  [-26, -4, 25, 87]\n",
      "\t2.  [-58, -39, -17, -11, -8, -3, 52, 74]\n",
      "\t3.  [-71, -68, -62, -50, -13, 35, 59, 67]\n",
      "\t4.  [-92, -31, -21, 15, 52, 69, 78, 83, 87, 98]\n",
      "Expected: [-92, -71, -68, -62, -58, -50, -39, -31, -26, -21, -17, -13, -11, -8, -4, -3, 15, 25, 35, 52, 52, 59, 67, 69, 74, 78, 83, 87, 87, 98]\n",
      "Result:   [-92, -71, -68, -62, -58, -50, -39, -31, -26, -21, -17, -13, -11, -8, -4, -3, 15, 25, 35, 52, 52, 59, 67, 69, 74, 78, 83, 87, 87, 98]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 5/5\n",
      "\n",
      "Test #6:\n",
      "Input lists:\n",
      "\t1.  [-69, -53, -46, -26, 0, 35, 49, 51, 55]\n",
      "\t2.  [-55, -39, -9, -8, 38, 93, 95]\n",
      "Expected: [-69, -55, -53, -46, -39, -26, -9, -8, 0, 35, 38, 49, 51, 55, 93, 95]\n",
      "Result:   [-69, -55, -53, -46, -39, -26, -9, -8, 0, 35, 38, 49, 51, 55, 93, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 6/6\n",
      "\n",
      "Test #7:\n",
      "Input lists:\n",
      "Expected: []\n",
      "Result:   []\n",
      "Test PASSED\n",
      "Passed to tested ratio: 7/7\n",
      "\n",
      "Test #8:\n",
      "Input lists:\n",
      "\t1.  [-78, -63, -61, -25, 15, 38, 45, 58, 67]\n",
      "\t2.  [-100, -94, -56, -50, -16]\n",
      "\t3.  [-93, -40, -39, -9, 17, 17, 84]\n",
      "\t4.  [-93, -68, -51, -48, -47, -43, -18, 13, 37]\n",
      "\t5.  [1, 38, 52, 58, 79, 80]\n",
      "Expected: [-100, -94, -93, -93, -78, -68, -63, -61, -56, -51, -50, -48, -47, -43, -40, -39, -25, -18, -16, -9, 1, 13, 15, 17, 17, 37, 38, 38, 45, 52, 58, 58, 67, 79, 80, 84]\n",
      "Result:   [-100, -94, -93, -93, -78, -68, -63, -61, -56, -51, -50, -48, -47, -43, -40, -39, -25, -18, -16, -9, 1, 13, 15, 17, 17, 37, 38, 38, 45, 52, 58, 58, 67, 79, 80, 84]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 8/8\n",
      "\n",
      "Test #9:\n",
      "Input lists:\n",
      "\t1.  [-96, -84, 33, 41, 48, 54, 81, 87, 100]\n",
      "Expected: [-96, -84, 33, 41, 48, 54, 81, 87, 100]\n",
      "Result:   [-96, -84, 33, 41, 48, 54, 81, 87, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 9/9\n",
      "\n",
      "Test #10:\n",
      "Input lists:\n",
      "\t1.  [-69, -63, -34, -17, -14, -3, 42, 69, 75]\n",
      "\t2.  [-99, -95, -69, 72, 89]\n",
      "\t3.  [-81, -4, 23, 37, 43, 88]\n",
      "\t4.  [-45, 3, 43, 78, 80, 82]\n",
      "\t5.  [-42, 11]\n",
      "\t6.  [-6, 14, 15, 59, 67, 92]\n",
      "\t7.  [-75, -61, -3, -1, 2, 3, 7, 14, 17]\n",
      "\t8.  [-75, -57, -49, -38, -15]\n",
      "\t9.  [-92, 5, 10, 43, 44, 92]\n",
      "\t10.  [-83, -59, -29, -20, -17, 7, 19, 26, 59, 80]\n",
      "Expected: [-99, -95, -92, -83, -81, -75, -75, -69, -69, -63, -61, -59, -57, -49, -45, -42, -38, -34, -29, -20, -17, -17, -15, -14, -6, -4, -3, -3, -1, 2, 3, 3, 5, 7, 7, 10, 11, 14, 14, 15, 17, 19, 23, 26, 37, 42, 43, 43, 43, 44, 59, 59, 67, 69, 72, 75, 78, 80, 80, 82, 88, 89, 92, 92]\n",
      "Result:   [-99, -95, -92, -83, -81, -75, -75, -69, -69, -63, -61, -59, -57, -49, -45, -42, -38, -34, -29, -20, -17, -17, -15, -14, -6, -4, -3, -3, -1, 2, 3, 3, 5, 7, 7, 10, 11, 14, 14, 15, 17, 19, 23, 26, 37, 42, 43, 43, 43, 44, 59, 59, 67, 69, 72, 75, 78, 80, 80, 82, 88, 89, 92, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 10/10\n",
      "\n",
      "Test #11:\n",
      "Input lists:\n",
      "\t1.  [-37, 13, 44, 89]\n",
      "\t2.  [-93, -91, -33, -32, -14, 57, 66, 85]\n",
      "\t3.  [-82, -77, -38, -5, 34, 61]\n",
      "\t4.  [-33, -4, 8, 18, 25, 33, 42]\n",
      "\t5.  [-92, -30, 30, 71, 74, 86]\n",
      "Expected: [-93, -92, -91, -82, -77, -38, -37, -33, -33, -32, -30, -14, -5, -4, 8, 13, 18, 25, 30, 33, 34, 42, 44, 57, 61, 66, 71, 74, 85, 86, 89]\n",
      "Result:   [-93, -92, -91, -82, -77, -38, -37, -33, -33, -32, -30, -14, -5, -4, 8, 13, 18, 25, 30, 33, 34, 42, 44, 57, 61, 66, 71, 74, 85, 86, 89]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 11/11\n",
      "\n",
      "Test #12:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [-84, -80, -34, 0, 56, 59, 75, 78, 96]\n",
      "\t3.  [-81, -64, -46, -20, 78, 79, 80]\n",
      "\t4.  [-34, -23, 54, 85]\n",
      "\t5.  [30, 34]\n",
      "\t6.  [-28, -16, 4, 26, 45, 56, 58, 80]\n",
      "\t7.  [-78, -46, 17, 17, 30, 73]\n",
      "\t8.  [-80, -60, -39, -33, 55, 69]\n",
      "\t9.  [-81, 41, 76, 92]\n",
      "\t10.  [-85, -63, -52, -51, -29, 14, 17, 49, 91, 97]\n",
      "Expected: [-85, -84, -81, -81, -80, -80, -78, -64, -63, -60, -52, -51, -46, -46, -39, -34, -34, -33, -29, -28, -23, -20, -16, 0, 4, 14, 17, 17, 17, 26, 30, 30, 34, 41, 45, 49, 54, 55, 56, 56, 58, 59, 69, 73, 75, 76, 78, 78, 79, 80, 80, 85, 91, 92, 96, 97]\n",
      "Result:   [-85, -84, -81, -81, -80, -80, -78, -64, -63, -60, -52, -51, -46, -46, -39, -34, -34, -33, -29, -28, -23, -20, -16, 0, 4, 14, 17, 17, 17, 26, 30, 30, 34, 41, 45, 49, 54, 55, 56, 56, 58, 59, 69, 73, 75, 76, 78, 78, 79, 80, 80, 85, 91, 92, 96, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 12/12\n",
      "\n",
      "Test #13:\n",
      "Input lists:\n",
      "\t1.  [-43, 23]\n",
      "\t2.  [-69]\n",
      "\t3.  [-100, -89, -82, -39, -31]\n",
      "\t4.  [-34, -29, -27, -18, 40, 75]\n",
      "\t5.  [-71, -61, -39, -6, 74]\n",
      "\t6.  [-87, -80, -66, -65, -41, -36, -23, 38, 56, 76]\n",
      "\t7.  [-95, -71, 35, 44, 65, 95]\n",
      "\t8.  []\n",
      "\t9.  [-25]\n",
      "Expected: [-100, -95, -89, -87, -82, -80, -71, -71, -69, -66, -65, -61, -43, -41, -39, -39, -36, -34, -31, -29, -27, -25, -23, -18, -6, 23, 35, 38, 40, 44, 56, 65, 74, 75, 76, 95]\n",
      "Result:   [-100, -95, -89, -87, -82, -80, -71, -71, -69, -66, -65, -61, -43, -41, -39, -39, -36, -34, -31, -29, -27, -25, -23, -18, -6, 23, 35, 38, 40, 44, 56, 65, 74, 75, 76, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 13/13\n",
      "\n",
      "Test #14:\n",
      "Input lists:\n",
      "\t1.  [-100, -89, 11, 34]\n",
      "\t2.  [-72, -64, -50, 33, 92]\n",
      "\t3.  [-81, -63, -62, -59, -52, -48, -29, 46, 57]\n",
      "\t4.  [0, 16, 48, 81, 97]\n",
      "\t5.  [-91, -50, 24, 41, 51, 64, 70, 84]\n",
      "\t6.  []\n",
      "\t7.  [-87, -53, -18, 14, 17, 33, 63, 83, 85]\n",
      "\t8.  [-92, -33, -21, -11, -8]\n",
      "Expected: [-100, -92, -91, -89, -87, -81, -72, -64, -63, -62, -59, -53, -52, -50, -50, -48, -33, -29, -21, -18, -11, -8, 0, 11, 14, 16, 17, 24, 33, 33, 34, 41, 46, 48, 51, 57, 63, 64, 70, 81, 83, 84, 85, 92, 97]\n",
      "Result:   [-100, -92, -91, -89, -87, -81, -72, -64, -63, -62, -59, -53, -52, -50, -50, -48, -33, -29, -21, -18, -11, -8, 0, 11, 14, 16, 17, 24, 33, 33, 34, 41, 46, 48, 51, 57, 63, 64, 70, 81, 83, 84, 85, 92, 97]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 14/14\n",
      "\n",
      "Test #15:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [-17, 15, 25, 61, 73, 100]\n",
      "Expected: [-17, 15, 25, 61, 73, 100]\n",
      "Result:   [-17, 15, 25, 61, 73, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 15/15\n",
      "\n",
      "Test #16:\n",
      "Input lists:\n",
      "\t1.  [-80, -80, -44, -29, 65, 70, 91]\n",
      "\t2.  [-88, -67, -55, -49, -21, -6, 27]\n",
      "\t3.  [-81, -78, -38, -12, -9, 26, 73, 74, 96]\n",
      "\t4.  [-89, -63, 14, 24, 53, 65, 84, 86, 94, 95]\n",
      "\t5.  []\n",
      "\t6.  [-87, -52, -34, 2, 64, 95]\n",
      "\t7.  []\n",
      "\t8.  [-71, -47, -36, -25, -22, 61, 69, 91]\n",
      "\t9.  [-90, -24, -13]\n",
      "\t10.  [-43, -32, -26, -14, -10, 69]\n",
      "Expected: [-90, -89, -88, -87, -81, -80, -80, -78, -71, -67, -63, -55, -52, -49, -47, -44, -43, -38, -36, -34, -32, -29, -26, -25, -24, -22, -21, -14, -13, -12, -10, -9, -6, 2, 14, 24, 26, 27, 53, 61, 64, 65, 65, 69, 69, 70, 73, 74, 84, 86, 91, 91, 94, 95, 95, 96]\n",
      "Result:   [-90, -89, -88, -87, -81, -80, -80, -78, -71, -67, -63, -55, -52, -49, -47, -44, -43, -38, -36, -34, -32, -29, -26, -25, -24, -22, -21, -14, -13, -12, -10, -9, -6, 2, 14, 24, 26, 27, 53, 61, 64, 65, 65, 69, 69, 70, 73, 74, 84, 86, 91, 91, 94, 95, 95, 96]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 16/16\n",
      "\n",
      "Test #17:\n",
      "Input lists:\n",
      "\t1.  [-87, -80, 17, 20, 47, 55, 59, 64, 85]\n",
      "\t2.  [-95, -61, -52, -18, -15, 0, 2, 4, 93, 93]\n",
      "\t3.  [-59, -34, 62]\n",
      "\t4.  [-95, -66, -37, -23, 35, 96]\n",
      "\t5.  [-99, -70, -63, -29, -27, 92, 97]\n",
      "\t6.  [-77, -56, -49]\n",
      "\t7.  [-75, -67, -26, -25, 77, 82, 91, 96]\n",
      "\t8.  [-88, -79, -51, 18, 59, 63, 63, 69, 100]\n",
      "\t9.  [-83, -36, -31, 70]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t10.  [16, 50]\n",
      "Expected: [-99, -95, -95, -88, -87, -83, -80, -79, -77, -75, -70, -67, -66, -63, -61, -59, -56, -52, -51, -49, -37, -36, -34, -31, -29, -27, -26, -25, -23, -18, -15, 0, 2, 4, 16, 17, 18, 20, 35, 47, 50, 55, 59, 59, 62, 63, 63, 64, 69, 70, 77, 82, 85, 91, 92, 93, 93, 96, 96, 97, 100]\n",
      "Result:   [-99, -95, -95, -88, -87, -83, -80, -79, -77, -75, -70, -67, -66, -63, -61, -59, -56, -52, -51, -49, -37, -36, -34, -31, -29, -27, -26, -25, -23, -18, -15, 0, 2, 4, 16, 17, 18, 20, 35, 47, 50, 55, 59, 59, 62, 63, 63, 64, 69, 70, 77, 82, 85, 91, 92, 93, 93, 96, 96, 97, 100]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 17/17\n",
      "\n",
      "Test #18:\n",
      "Input lists:\n",
      "\t1.  [-4, 40, 54, 78]\n",
      "\t2.  [5, 51, 74]\n",
      "\t3.  [-87, -72, -42, -25, -20, 12, 62]\n",
      "\t4.  [-99, -69, -8, 15, 34, 37, 81, 93, 95]\n",
      "\t5.  [-37, -29, -24, -13, -5, 69, 82]\n",
      "Expected: [-99, -87, -72, -69, -42, -37, -29, -25, -24, -20, -13, -8, -5, -4, 5, 12, 15, 34, 37, 40, 51, 54, 62, 69, 74, 78, 81, 82, 93, 95]\n",
      "Result:   [-99, -87, -72, -69, -42, -37, -29, -25, -24, -20, -13, -8, -5, -4, 5, 12, 15, 34, 37, 40, 51, 54, 62, 69, 74, 78, 81, 82, 93, 95]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 18/18\n",
      "\n",
      "Test #19:\n",
      "Input lists:\n",
      "\t1.  []\n",
      "\t2.  [-2, 15, 54, 81, 92]\n",
      "Expected: [-2, 15, 54, 81, 92]\n",
      "Result:   [-2, 15, 54, 81, 92]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 19/19\n",
      "\n",
      "Test #20:\n",
      "Input lists:\n",
      "\t1.  [-57, -32, -14, -11, 18, 39, 56, 78]\n",
      "\t2.  [-85, -20, 59, 90]\n",
      "\t3.  [-69, -61, -56, -51, -46, 63, 64, 76]\n",
      "\t4.  [-95, -85, -46, -34, -9, 11, 65, 79]\n",
      "\t5.  [-91, 67, 89, 94]\n",
      "\t6.  [-93, -68, -60, -32, -7, -3]\n",
      "\t7.  [-25]\n",
      "\t8.  [-87, -17, -9, 3, 7, 72, 85, 86]\n",
      "Expected: [-95, -93, -91, -87, -85, -85, -69, -68, -61, -60, -57, -56, -51, -46, -46, -34, -32, -32, -25, -20, -17, -14, -11, -9, -9, -7, -3, 3, 7, 11, 18, 39, 56, 59, 63, 64, 65, 67, 72, 76, 78, 79, 85, 86, 89, 90, 94]\n",
      "Result:   [-95, -93, -91, -87, -85, -85, -69, -68, -61, -60, -57, -56, -51, -46, -46, -34, -32, -32, -25, -20, -17, -14, -11, -9, -9, -7, -3, 3, 7, 11, 18, 39, 56, 59, 63, 64, 65, 67, 72, 76, 78, 79, 85, 86, 89, 90, 94]\n",
      "Test PASSED\n",
      "Passed to tested ratio: 20/20\n",
      "\n",
      "===== Final results: =====\n",
      "Total tests passed: 20/20\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "test_merging(create_linked_list, linked_list_to_list, merge_lists)\n",
    "# test_merging(create_linked_list, linked_list_to_list, merge_sorted_lists,\n",
    "#             samples=100, lists_counts=(0, 100), lists_lengths=(0, 100),\n",
    "#             failed_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Porównanie wydajności"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===== Results after 5 tests: =====\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 0.3041115 \tAverage: 0.0608223\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 0.3190944 \tAverage: 0.0638189\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 0.3463099 \tAverage: 0.0692620\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 0.4014821 \tAverage: 0.0802964\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 1.0236990 \tAverage: 0.2047398\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 1.5471632 \tAverage: 0.3094326\n",
      "\n",
      "===== Results after 10 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 0.6556153 \tAverage: 0.0655615\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 0.6826472 \tAverage: 0.0682647\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 0.6826975 \tAverage: 0.0682698\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 0.8543885 \tAverage: 0.0854388\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 2.1582413 \tAverage: 0.2158241\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 3.2602713 \tAverage: 0.3260271\n",
      "\n",
      "===== Results after 15 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 0.9451699 \tAverage: 0.0630113\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 0.9548988 \tAverage: 0.0636599\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 0.9706008 \tAverage: 0.0647067\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 1.1807837 \tAverage: 0.0787189\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 3.0079267 \tAverage: 0.2005284\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 4.5228140 \tAverage: 0.3015209\n",
      "\n",
      "===== Results after 20 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 1.0196807 \tAverage: 0.0509840\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 1.0495369 \tAverage: 0.0524768\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 1.0526979 \tAverage: 0.0526349\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 1.2988036 \tAverage: 0.0649402\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 3.3321352 \tAverage: 0.1666068\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 4.9769468 \tAverage: 0.2488473\n",
      "\n",
      "===== Results after 25 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 1.1944108 \tAverage: 0.0477764\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 1.2075403 \tAverage: 0.0483016\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 1.2145720 \tAverage: 0.0485829\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 1.5025690 \tAverage: 0.0601028\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 3.9415708 \tAverage: 0.1576628\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 5.8578310 \tAverage: 0.2343132\n",
      "\n",
      "===== Results after 30 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 1.3474751 \tAverage: 0.0449158\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 1.3490114 \tAverage: 0.0449670\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 1.3579998 \tAverage: 0.0452667\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 1.6669343 \tAverage: 0.0555645\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 4.5649793 \tAverage: 0.1521660\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 6.5882282 \tAverage: 0.2196076\n",
      "\n",
      "===== Results after 35 tests: =====\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 1.7611933 \tAverage: 0.0503198\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 1.7844059 \tAverage: 0.0509830\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 1.7906456 \tAverage: 0.0511613\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 2.1738863 \tAverage: 0.0621110\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 5.8449950 \tAverage: 0.1669999\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 8.5119257 \tAverage: 0.2431979\n",
      "\n",
      "===== Results after 40 tests: =====\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 2.1177239 \tAverage: 0.0529431\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 2.1328533 \tAverage: 0.0533213\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 2.1439633 \tAverage: 0.0535991\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 2.6802707 \tAverage: 0.0670068\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 7.0184255 \tAverage: 0.1754606\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 10.2018578 \tAverage: 0.2550464\n",
      "\n",
      "===== Results after 45 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 2.3800950 \tAverage: 0.0528910\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 2.3920372 \tAverage: 0.0531564\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 2.4017136 \tAverage: 0.0533714\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 2.9931355 \tAverage: 0.0665141\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 7.8299096 \tAverage: 0.1739980\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 11.4444158 \tAverage: 0.2543204\n",
      "\n",
      "===== Results after 50 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 2.5814643 \tAverage: 0.0516293\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 2.6153164 \tAverage: 0.0523063\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 2.6212485 \tAverage: 0.0524250\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 3.2815890 \tAverage: 0.0656318\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 8.5904243 \tAverage: 0.1718085\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 12.6117656 \tAverage: 0.2522353\n",
      "\n",
      "===== Results after 55 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 2.7848139 \tAverage: 0.0506330\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 2.8197021 \tAverage: 0.0512673\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 2.8366992 \tAverage: 0.0515763\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 3.5309958 \tAverage: 0.0641999\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 9.2844708 \tAverage: 0.1688086\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 13.6470318 \tAverage: 0.2481279\n",
      "\n",
      "===== Results after 60 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 3.0577927 \tAverage: 0.0509632\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 3.0943120 \tAverage: 0.0515719\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 3.1014476 \tAverage: 0.0516908\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 3.8298299 \tAverage: 0.0638305\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 10.0964928 \tAverage: 0.1682749\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 14.9111383 \tAverage: 0.2485190\n",
      "\n",
      "===== Results after 65 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 3.3642116 \tAverage: 0.0517571\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 3.4364538 \tAverage: 0.0528685\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 3.4792461 \tAverage: 0.0535269\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 4.2136359 \tAverage: 0.0648252\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 11.0165024 \tAverage: 0.1694847\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 16.5231612 \tAverage: 0.2542025\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===== Results after 70 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 3.7223146 \tAverage: 0.0531759\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 3.7365427 \tAverage: 0.0533792\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 3.8165803 \tAverage: 0.0545226\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 4.5947332 \tAverage: 0.0656390\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 11.9914386 \tAverage: 0.1713063\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 18.1701338 \tAverage: 0.2595733\n",
      "\n",
      "===== Results after 75 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 3.9884555 \tAverage: 0.0531794\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 4.0123091 \tAverage: 0.0534975\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 4.1699085 \tAverage: 0.0555988\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 4.9428897 \tAverage: 0.0659052\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 12.9063532 \tAverage: 0.1720847\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 19.6090527 \tAverage: 0.2614540\n",
      "\n",
      "===== Results after 80 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 4.1940424 \tAverage: 0.0524255\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 4.2027829 \tAverage: 0.0525348\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 4.3602676 \tAverage: 0.0545033\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 5.1891096 \tAverage: 0.0648639\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 13.5233607 \tAverage: 0.1690420\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 20.4954414 \tAverage: 0.2561930\n",
      "\n",
      "===== Results after 85 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 4.5140643 \tAverage: 0.0531066\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 4.5492299 \tAverage: 0.0535204\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 4.6845787 \tAverage: 0.0551127\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 5.5951040 \tAverage: 0.0658248\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 14.4960423 \tAverage: 0.1705417\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 21.9439993 \tAverage: 0.2581647\n",
      "\n",
      "===== Results after 90 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 4.7539201 \tAverage: 0.0528213\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 4.7863507 \tAverage: 0.0531817\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 4.9297163 \tAverage: 0.0547746\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 5.8419127 \tAverage: 0.0649101\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 15.2328529 \tAverage: 0.1692539\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 22.9987602 \tAverage: 0.2555418\n",
      "\n",
      "===== Results after 95 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 5.1796887 \tAverage: 0.0545230\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 5.2636452 \tAverage: 0.0554068\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 5.3847327 \tAverage: 0.0566814\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 6.3733435 \tAverage: 0.0670878\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 16.5649471 \tAverage: 0.1743679\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 25.0327635 \tAverage: 0.2635028\n",
      "\n",
      "===== Results after 100 tests: =====\n",
      "(Sposób #1) (Implementacja #1) W miejscu funkcyjnie   Total (in seconds): 5.4547603 \tAverage: 0.0545476\n",
      " (Sposób #1) (Implementacja #1) W miejscu obiektowo   Total (in seconds): 5.5328946 \tAverage: 0.0553289\n",
      " (Sposób #1) (Implementacja #2) Z kolejką obiektowo   Total (in seconds): 5.6599693 \tAverage: 0.0565997\n",
      "     (Sposób #3) Z kolejką priorytetową po długości   Total (in seconds): 6.7774596 \tAverage: 0.0677746\n",
      "      (Sposób #2) Z kolejką priorytetową funkcyjnie   Total (in seconds): 17.4565210 \tAverage: 0.1745652\n",
      "       (Sposób #2) Z kolejką priorytetową obiektowo   Total (in seconds): 26.3758962 \tAverage: 0.2637590\n",
      "\n",
      "===== Final results: =====\n",
      "Tests performed: 100\n",
      "Total times (in seconds):\n",
      "\t(Sposób #1) (Implementacja #1) W miejscu funkcyjnie:   5.4547603\n",
      "\t (Sposób #1) (Implementacja #1) W miejscu obiektowo:   5.5328946\n",
      "\t (Sposób #1) (Implementacja #2) Z kolejką obiektowo:   5.6599693\n",
      "\t     (Sposób #3) Z kolejką priorytetową po długości:   6.7774596\n",
      "\t      (Sposób #2) Z kolejką priorytetową funkcyjnie:   17.4565210\n",
      "\t       (Sposób #2) Z kolejką priorytetową obiektowo:   26.3758962\n",
      "Average times (in seconds):\n",
      "\t(Sposób #1) (Implementacja #1) W miejscu funkcyjnie:   0.0545476\n",
      "\t (Sposób #1) (Implementacja #1) W miejscu obiektowo:   0.0553289\n",
      "\t (Sposób #1) (Implementacja #2) Z kolejką obiektowo:   0.0565997\n",
      "\t     (Sposób #3) Z kolejką priorytetową po długości:   0.0677746\n",
      "\t      (Sposób #2) Z kolejką priorytetową funkcyjnie:   0.1745652\n",
      "\t       (Sposób #2) Z kolejką priorytetową obiektowo:   0.2637590\n"
     ]
    }
   ],
   "source": [
    "compare_performance(algo_data,\n",
    "                    samples=100,\n",
    "                    lists_counts=(0, 1_000),\n",
    "                    lists_lengths=(0, 100),\n",
    "                    lists_values=(-1_000, 1_000),\n",
    "                    progress_interval=5\n",
    "                   )"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}